Even you implement every espect of human behaviour, unless there will be a major boost in the AI development, the best you could do is to produce a log of the events. A human must read this log and make it an history, decide what is important and what is not, and make a story out of it.

Think about it - your algorithm can produce an important meeting between the leaders of two nations, it will be able to write in the log what are the interests of each leader and what are the results on the meeting, but it wond be able to write what they say. The player will want to know that.
You program will be able to produce religions, maby some of their costumes, but it wont be able to write down the story behind each religion - god tales and such.

If you need a human to make a story out of the log, then the human can make the story himself.

Maybe you could link this up to the thread about alternate plots with the same ending, except swap "history" for "plot" and "beginning" for "ending".

Use some kind of semi-random template to decide which race or nation discovered the alien artifact, which one colonized the moon, and which one discovered magic, then match two of them up with a "war" relationship, and have the PC enter there. Same basic situations, just different names and places and flags.

This would work best, I think, with a game like Pirates! or Escape Velocity, where factions and characters are more modular.