(Of course, there are a few weirdo games like Minecraft that don't really have a story, but let's not drag them into this discussion).
Erhm...
Shall I spoil you then?
There is indeed a story, and an end of game credits roll if you do kill the dragon in "the Endworld"...
but upon interacting with other world entities a rising action builds, and depending upon how the player responds to said rising action more quests are generated and the plot is developed further.
Aside from the fact that the content is not generated, Skyrim comes pretty close to achieving this. A series of otherwise accidental events leads you into one or many of the main quest lines which are optional. Skyrim developers were however kind enough to provide a "main questline" as a fallback/tutorial.
The problem is, I can't think of any way to do this other than assigning predetermined quests after the player has reached a certain point within the game.
What worries me if not the procedural portion of your idea. To a certain extent, progress quest managed to do this fairly well, even though it was absurd.
The real challenge comes from taking into account previous quest to determine the following quests.Narrative plays a big part in getting events lined-up.
To put it simply, you need to emulate a tree of the different outcomes without knowing how to even begin or end any of the branches. I would recommend the use of advanced metrics. While a game like Ultima has nothing to do with this, the idea of virtues, and how you scale against each of them could be a start to determine where you're headed.
You could plant a few "non-generated quests" in the starting whereabouts of the game, and check against the player actions (much like the player must answer initial questions). This would determine what they are good at, and what they suck at, and you could either focus on their strengths as this would probably define their playstyle, or challenge the player by introducing his weaknesses (preferably, you'd do both). Your approach to define each quest should have parameters that would take into account certain threshold.
Example of the top of my head
Metrics:
- Courage (Would you fight or run, where a positive value is fight, negative is run)
- Piety/Sacrifice (Are you self-sacrificing, where positive is taking the blame or hit for someone else, and negative is taking care of self first)
Here's how they can play with one another or against:
- You encounter an enemy who is stronger than you (fight: courage+, run, courage-)
- You encounter a man that is up against a troll (fight: courage+, Piety+, run: courage-, piety-)
- A tribunal made of your pairs has found you guilty, do you fight them off? (fight: courage+, piety-, Run: courage-, piety+).
etc.
Now, assuming the player is good at courage, but sucks at piety, you'll try to put him in situations that challenge him from time to time by using the piety drawback against him or by bringing larger-than-real threats that he'll have to consider escaping. Also, because the player has clearly determined that he wants to fight, you'll put him more often than not in belligerent quests.
You can easily scale this by adding metrics, especially those that have common ground but that can also be turned against one another by the nature of the setting.
This wouldn't make a great story, but players are good at tying the knots.
The real downfall to such a system is that it would feel like a sandbox game, and ultimately, people resent that. When you figure out there's no "greater plan" and you're just toying with mechanics that are interacting in a complex but nearly predictable way, it tends to all fade.
I would recommend the inclusion of a final boss, and perhaps a final questline that has very little optional/custom content. When the time comes, whatever you metric is (say, "player_level==50", you can activate this questline and the player now has the option to complete the game. Alternatively, you could activate it at the very start, and let the player know what the endgame is, but that the journey is entirely up to them.
Which comes to show my last point: open up many paths. The big advantage of this system is that you are not confined to the intricate narrative of a regular game. Capitalize on this, open up more than one path. This will allow the player to express themselves, which in turn will refine your metrics, and will allow you to feedback even better quests.
Your initial issue is that you need information in order to tie the knots, and metrics help you achieve that. They even allow you to calibrate gameplay via your players' expressions.