What if you made every faction except for Sarranids and Swadia created by a random event?
For example, it could start with Calradia owning everything, and Sarranids owning the desert.
Then, a random event would take place making a peasant rebellion in the Vaegir lands, a coup could occur changing the Calradic empire into Swadia; and shortly after, Nords would appear at the top of the map (as in the sea) and sail to Calradia until they disembark and take over Wercheg, etc.
And perhaps there could be some NPCs in taverns so the player could align himself with those factions before they even get created.
Just thinking out loud here, I know it's big coding job, but it would be quite awesome to take part in the formation of modern Calradia.