Drop the player-centric written story altogether. Just build a game that plays itself regardless of the player, and if a written story there is, it should play itself too, vulnerable to player influence but not waiting for it. Good prototypes, although kind of simple because focused on some particular aspects, are Crusader Kings and Mount and Blade. Whatever you (the player) do, things go on around, NPCs interact with each other in a very dynamic way, situations gets solved and new ones arise, sometimes getting in the way of your own plans, sometimes finding you on the way of their plans.
Hilarity almost mechanically ensue. Just write some really complex npcs behaviors . Say npcs would have goals (being rich or famous - wishes for some types of object à la DF) "traits" (npcs is a merchant, or a warrior, or a merchant/warrior) some way to recognize it's environnement ("knows" the richness of other "merchant" types npcs of the same allegiance (civilization/region/town/guild/family...likely, your basic npc merchant would care about other merchants in town, the richest in town would care about the richest in the region, etc) then scripted ways to interact with the environnement to achieve goals.
So say our merchant...
-checks for "traits/goals" : goal "being rich",he's ok being the third in town, but he got the trait "greedy", so he wants to be first
-checks for wealth, says it's the third richest in town
-engage scripts "get richer" : example could be : - checks prices in town, determine most profitable trade, engage craftman npc of XX level in chosen trade (that could be the player)
-IF and only IF, the merchant has the "unlawful" trait,engage npc of "warrior" type, with "unlawful" trait, to start "assassination" script/quest ; now that could be the player, but it would happen as well regardless of the player, provided there is a "warrior" "unlawful" npc in town. For that matter, if the merchant is in fact a merchant/warrior, he could engage on the quest himself
-happened he also has traits "art lover", so he'd look for a npc(or the player) with the "explorer" or "adventurer" trait and ask for an item of "quality: => masterwork" "value =>50000 dwarf bucks" "age=> 50 years". Our player would go rob the nearest tomb but meet there members of cult XXX because :
Npc: grand priest of XXX
Goals: maintain religious followers =>50% town population
Now the game must be able to read, DF-room-quality-style, the total value of temples which would contribute to a "religion score" which would be rolled against peoples in the area of influence to see which religion (or lack of) they follow, with bonus and maluses if the leader of the civilization/faction/town/family is of the same religion, etc...
Possible "tools" "scripts" "quest": get MOAR value for the temple.
If we only had a few npcs types (merchant, craftman, priest, bard, scholar....) a few goals and a few "quest" with which they can interact with others npcs, based on actual numbers, on the real situation of the game world at that time (no "fetch me some random animal's part for the hundredeth time while the shop next door sells them in bulk and i don't actually really do anything with them i just put them in my magic pocket and puff ! they disappear then i get some gold out of my ass to reward you with" , but rather " if casualties to goblin over the past week =>15, then hire adventurer/warrior type to kill goblins--but if available gold=<XXX, then beg adventurer to kill goblin") then we'd have hilarity clusterfucks everyday.
I believe it's the way DF will works anyway.(but not on a micromanagement scale. yet.)
Then for the sake of hardware requirement you'd keep a maximum number of npc active at one time and abstract everything that is happening far away from the player.