Randomly generate a city full of people. Make a few dozen of them the important NPCs. Give them situations and goals, problems they need to solve and potential ways to solve them. Certain NPC's goals are opposite others'. Then drop the player into that world and have the 'quests' the player is performing be generated based on the NPCs needing their help.
Updates wouldn't be adding new hand-written stories, it would be adding more complexity, more goals, more problems, more things that can be, and the story would generate itself.
Done right, this would be incredible.