Following my post above, just cleaned up the last few lairs, the Arena quest, the Dragon statue quest, and three wildlands, (boss only in two of them, bunch of haunters with Morian in the third). Maybe 2 dozen fights in total.
With a dedicated trainer henchman, and the Sov as well as a henchman mage, I was able to get the Sov to 36, and both henchmen are 26, from 11 and 8. Troops are all 20s. A lot of the fights my Sov was getting close to 400 points. These were Deady-Epic mostly, couple of Strongs.
Haven't touched quest maps, except for two that I found, and I have used maybe 4000 points of Destiny's Insight, a lot of that was to level the trainer. Had to stop fighting to go buy spellbooks for the two henchmen, as they started running out of choices worth taking pretty quickly.
Still have a map full of AI factions, as well as the Master quest to go; that's a lot of levels available from a medium map. I'm guessing even with the split, adding a dedicated trainer to an army will mitigate at least some of the bleeding, and on a larger map shouldn't really be an issue, especially with the upcoming xp increase for fighting higher level armies. If you want high levels, make that first hero or your Sov a Commander, and max the training route. I didn't add the trainer to my force until my Sov was already 30, next game he'll be there from the get-go. Also wasn't using the Heroic trait on this build, leaving still more XP that could have been grabbed.
I'll try this out with a non Altar build after .91, and see how a multi-hero stack progresses, with multiple trainers.