I found this strategy to be really effective at turning the game around from dire doom to stable path to victory:

First I created a custom sovereign, picking disciplined, brilliant, hardy and quick - all traits designed to increase stats significantly; furthermore on every level up I preferentially took traits that increase stats more. I also happened to have 3 shards and one champion to help me out. Things went okay until I got more and more pressed in my single city by Altar and Capitar who vied for me to declare war on the other. I kept stalling until they finally both declared war on me in the space of 2 turns. Swiftly I lost all my external resources and had to use all my tactical acumen to just fend off the excess hordes assaulting my capital. I had a few units as well as my level 6 sovereign and champion left.

Finally in desperation I started the main point of my strategy that I had been building up for: spend all the accumulated mana (almost 2000) as well as my sovereigns high all-round stats to continuously cast Paragon. By the time I ran out of mana (my sovereign still had enough stats for 4 casts left) my champion had progressed from level 6 to level 26. A really big step forward. The champion was now enough to chase all enemy armies from my lands and start conquering enemy cities.

I'm now busy researching towards champion-gear (and other items that grant per-level bonuses).