Procedurally generated story, does it work?

Short answer:
I don't know of any games that have succeeded in doing this. Would love to play one. I've been working towards something similar, although my approach is very abstract in order to avoid being bogged down by the huge AI requirements needed for really good character level simulation.

Long answer:
I believe repetition will greatly depend on the variety of interactions the nations or powers themselves can have. I imagine that it is no different from a situation where you are playing as a nation and can only attack-- your "story" of what you did in the game will be EXTREMELY repetitive ("I attacked Rome, then I attacked Naples, then Rome was attacked" etc.)

If attacks themselves have some variety that helps alleviate some repetition: You might tell a story of being besieged, of entrenching and barely surviving through the night. The story might be more interesting with detail ("our archers pummeled their swordsman, but were driven back by the catapults on the hill.")

If units can impact each other in highly creative, asymmetrical ways, you'll get even more variety. Perhaps you have priests or diplomats that travel ("stack") with armies. They can create stories like "we were evenly matched but our scions prayed to the gods such that even the heathens heard and joined our side (though they needed a few thousand gold as an incentive)." (e.g., Diplomat ability in old Civilization or priest ability in Age of Empires)

If you take this level of detail and turn it into more granular mission objectives, I think repetition becomes a bit less likely. It may still be "attack this town" or "attack this army" but gameplay turns on the nuance of how. Maybe you "attack this town" by bribing the leader then betraying and executing him, saving your lord a few thousand gold. Maybe you have to take out the heavily defended catapults before a battle, saving an army from being slaughtered.

Despite all of this I think you'll still have repetition. To help combat this I'm a big fan of using controlling variables to guide the experience from a high level. If, for instance, you've bribed & killed leaders some stat should track this and automatically up the difficulty for doing so (a reputation stat might work here). Or if there's too much warfare, allow peace to break out or disaster to intervene, even if only temporarily.

I think there's lots of room for potential, but ultimately your definition of "story" may have to bend a bit.

You might want to look at squidi.net
In the 300 game designs section, he has a bunch involving PGC.

I've never seen a game that does it well, although people love to talk about it. What attempts usually wind up with is either too much scripting that makes it feel samey while throwing in procedurally generated characters, or a series of genuinely emergent situations that are either mundane or nonsensical. You'll run into a real uncanny valley dilemma.

The benefit of writing is that a human author is using their talent and ability to craft a story that has a purpose, and a tone, and an art to it. A badly written story is a thousand times better than a simulation of story-writing.

Dwarf Fortress has a "Legends" mode, where you can review all the historical events and characters from the procedural worldgen. I've genned dozens of worlds, and I'm sure hundreds of thousands have been run around the world, and Legends is always a somewhat sad joke, crazy dudes doing random stuff and behaving so simply that the bones of the simulation jut out at odd angles, giving it a robotic, emaciated look. There's the occasional gem, but it's a needle in a haystack.

And that's my favorite procedural game ever.

It would have to be a layered simulation, using a RNG and a bunch of archetypes to decide relationships and forge dramatic situations. Make a little script for some of Polti's 36 situations, and use a bit of logic to define each role, and then work through your characters and find conflicts that can be resolved.

So for instance, randomly gen up a simple world, with three villages of 20 people each, and then start assigning relationships to them. This village and that village are at war. This village is wealthy, that one is poor. These two villages depend upon resources that only the other produces. Then whip of 4 or 5 characters for each village, non-generic townsfolk who have hopes and dreams and ideals. Then form some relationships between these fleshed-out people. Stranger, lover, nemesis, kinsman, throw tags around like there's no tomorrow, and then you can try to parse them into archetypes relative to one another. Can one be considered ambitious? Assign him an object to covet and then pick someone associated with that object to be his adversary, and voila! Drama!

Then just have a suite of quests or player activities linked to each situation, so the player an get involved and have some emergent gameplay.

I figure it won't take more than forty or fifty years to overcome all the obstacles there.

I think you could set the world up as a simulation of sorts, with hand written quests added wherever appropriate. In general I think you can do randomly generated or procedurally generated quests. But I don't think you can do procedurally generated plot.

Stories are not quite like reality, they represent the interesting bits. You can set the NPCs to be more prone to traditionally interesting things, but this behavior then becomes humdrum within the game. Yet another royal assassin? Boring!

I think the only way a game can spit out interesting stories is when there is hand written content you haven't seen yet.

I went to the GDC in Lyon a few years ago and there was also a lecture (i can't remember what it was called but will try to look it up) on this topic.
Basically he developed relations and interactions between all his colored blobs, this based on about 40 (changing) parameters each blob had. This happened on an individual & group level (1 group: all the blobs of the same color). This created some interesting situations (& was imho a p. good way of quickly prototyping such behaviour).
If you'd take something like this as the basis and then add (partial) knowledge of these actions from other blobs to the model to trigger new reactions based on the blobs' own parameters & prior history this would induce some pretty neat behaviour.

Also, as Wavinator said, there should be all kind of action going on. You could drive this very far.

People could migrate somewhere or stay. Maybe buy and throw out or give away stuff. Have relationships, have kids. Have accidents. There could be wars driving almost everyone out of a certain area only to have it bewilder. You could start random fires in forests and cities... really the options are endless.

It hasn't been properly done before and making a believable implementation would be very hard but such games are definitely the way to go...

that sounds so intresting to see, but also so hard that only a group of programmers coworking with writters could do it (maybe not that extreme, but away from my reach right now). I missexplained, i don't seek a main plot, to be PG, just a backstory, something to read from newspapers and that you can end up changing with your actions, like you are assigned to delivar X piece of important information (troop/fleet movement, weapons plans, secret comunication codes) and if you want, you can sell it to your enemy for a lot more money, but then the first nation will persectute you, also will change the way of war and maybe who will win.

There's one game that does interactive procedural stories: Facade

http://www.interactivestory.net/

Supposedly the tech is already being licensed. There's papers up on the site about it.