Is that 一个 really necessary;
No. Its presence stresses that there is one and only one story.
No, it is acceptable without as well.
Whats the difference between having the dou or leaving it out?
每个 and 都 work in concert for emphasis. Speakers can and will leave out one or the other with no radical change in meaning.
每个……都 is a common paring in this case, so it'd sound smoother i.e. better with it.
Then it should accept the answer without the 都
Reported "每个汉字有一个故事吗？" to be accepted.
I just got this right! From the first time!! :D