This is a very good idea, but one which requires too much research and development for an independent commercial software developer. I have been slowly working towards this lofty goal with the research and development of open source middleware for multimedia authoring and videogame creation for the past 20 years and am not even close to releasing product.
You see, I am increasingly nauseated by the current trend towards Cinematic Videogames.
It is a phrase that I regard as something of an oxymoron.
Developers could remedy this by realising that narrative is merely a symptom of an underlying theme. If it is the intention of the artist to convey this theme, then what does it matter to hold to a particular pre-scripted narrative?
Games are systems of rules within which interesting behaviour may emerge, often with some aspect of challenge, or competition for the player to measure their performance against. The designers of Chess and Football didn't need to fret about "Story", but despite this stories still emerged from interesting games:
http://en.wikipedia.org/wiki/World_Chess_Championship_1972
http://en.wikipedia.org/wiki/Maradona#1986_World_Cup
However, there are a great many more matches that were dull. Being a passive spectator does not really help with engagement, yet the ideal would be to 'rig' the match so that the opponent either made deliberate mistakes, or suddenly got a whole lot better (e.g. equalising just before half-time).
Once the game's rules have been modified to make it seek entertaining levels of drama rather than boring old fairness the player's psychology can be probed by offering them a choice of actions (NPC proposed procedurally-generated missions), the successful completion of which would gain you "Kudos" for your competent role play and unlock more challenging and subtle missions as the game's personality model of the player's "alter-ego" was further refined.
This would allow games to get away from the thinly disguised corridor along which revelatory narrative scenes are encountered in the correct sequence. A game may seem to then be an Open World, but on extended interaction the player would find their choices constrained by their past actions and probably be oblivious to the subtle interventions of the game shaping the set of available choices (and their consequences), throughout in order to reinforce the underlying theme - forcing irreversible character developments, then stage-managing a cathartic climax.
Players would assume roles and try to play that part as best as they could being rewarded with Kudos for remaining "in character". Counter-intuitively, this would herald a break from players avoiding character death as this would no longer mean GAME OVER.
Indeed, heroic sacrifice, or a villain getting his comeuppance, could both be terminal for the player's character, but pay a handsome reward in terms of Kudos. The player would continue with the game, selecting from a choice of new, equivalently experienced, characters - adding equipment in keeping to the new role they were adopting from a cash sum each character had been allotted. As a result, play would have a different, dramatic, motivation rather than mere, hackneyed, survival and because the story was built in response to player psychology they would more likely be drawn in to its emergent story.
So, in summary:
Randomly generate? No.
Procedurally-generate in harmony with player psychology and a coherent theme? Yes.