Have you played Crusader Kings II? (I believe Europa Universalis might do the same, but it has been so long since I played EUIII, and haven't touched EUIV yet.)
They use a system of 'events' that trigger based on various factors and fill in various character names as needed. A handful of them are longer scripted events with some random factors thrown in, which build a tree of a handful of these popups that are linked, but most are just one off popups "So and So had a dispute with This other guy, Side with So and So to make them happy, side with Other Guy to make them happy, or take a middle ground that doesn't make either side upset with you." kind of things.
You could use something like that to string together a sort of "Pick your own adventure" book for a storyline and build a system that feeds into the 4x game (Bonuses, unlocks, rebellions, etc.) which in turn feeds back into the 'story engine' (Doing well putting down a rebellion feeds back in and may trigger event paths that give you choices that can lead to bonuses, or maybe you choose poorly and the rebellion leader becomes a martyr and your empire spirals out of control with rebellions.)