Sions with the Trainer traits will also help (if they can get them; it's been a while since I bothered with Sions), if you're playing an Empire, since Henchmen are only available to the Race of Men (default faction Altar).

Increasing quest frequency in game setup or spamming quest maps in game will also help, as will davrovana's suggestion of increasing the world difficulty. If you didn't take the faction trait that grants quest maps, Altar might have them for sale in its shop, if they've researched the tech for it (as might any custom faction with the right trait).

A great deal of patience and farming AI armies can also do it.

Not clearing out things that spawn wandering monsters and then killing whatever does spawn will help (generally speaking, this is worth more experience than AI armies are, even if the spawn is a Bandit and his pet wolf, but you need to keep the AI from clearing it or you just lost your experience farm, and I would tend to recommend that you not leave a whole lot of such things around if they're within your area of influence, because the lair guards will tend to wander off, making it that much easier for a random AI champion to raze the lair).

There is also a mage perk that gives you 25% xp bump in addition to the ones you mentioned.  As Davrona points out, you can also get a commander in your army with the multiple perks goving xp bumps, for a total of 40% and those apply to your whole army.  Of course the game is more than half over by that point.

Honestly, I have never paid that much attention to my champions level by teh end of the game.  Probably 15 to 18.  I know that when I play mages, they can pretty much max out one path of the mage tree, either summoning or the branch that increases spell mastery/damage, but not both.  I tend to specialize, so level 15 is enough. 

I have played on all map sizes but the huge random map with epic pacing and challinging AI is my favorite.  I pretty much leave everything else at the default levels.

I've gotten a champion as far as level 25, but only on huge maps. You have to put some effort into finding and attacking the highest-level monster camps before enemy factions do, and make sure you're using the "Tutelage" spell when you attack. But even if you don't optimize XP, level 15 is pretty respectable for anyone except mages specializing in the "Evoker" branch. I generally stop worrying about my champions around level 12-13 and focus on the weaker ones.

I'd just point out that it's actually better, at least from a long-term leveling multiple champions up perspective, to leave strong monster camps alone and just hunt down and kill the spawns that come from them, rather than actually clearing the lair. Leaving the guardian stack alone tends to help keep the AI from clearing it out, as will blocking off the AI's access to the monster spawning area in some way.

It's still very slow, though, and if you're just focusing on one champion it's probably not worth it.

This I can definitely agree with, especially given just how much time it takes to get anything to level 20.

Just to let you know the result when playing a huge map with world difficulty insane and quest probability plenty.

Finally my hero was level 20 (17 when I was playing normal world difficulty and normal quest frequence).
So it is giving 2-3 levels more but not enough. I will now look for the Lost Forge mod and hopefully get where I want to get.

Note: I know that it is not necessary to have such an overpowered hero to win the game on any difficulty level. But I would like to know how fights are if a warrior has nearly all traits.

Thanks for help,
Makkaroni

Played Lost Forge Mod. My Sovereign ends up at Level 22 and I could nearly select all traits I want.

But at all it is not what I want. I think I'm looking more for a scenario where I can take my heroes through 4-5 huge maps. Is something like that existing?

Paragon costs the sovereign 5 health permanently with each casting and only affects 1 champion per cast, and requires that the caster has at least 6 maximum health, while Crusade only affects trained units. Destiny's Insight might be doable, but at only 25 experience per cast you'll be spending quite a bit of time casting it to buy any of the higher champion levels. Paragon additionally cannot target the sovereign.

Destiny's Gift and Blood Curse can be used to make up for the health cost of Paragon, however, but can cost quite a bit of mana (to make up the Paragon-induced health losses, you'll require at least two castings of Destiny's Gift, so that combination has a minimum cost of roughly 390 mana if you get lucky and get the health bonus with every casting of Destiny's Gift, at least once you drain your sovereign's health down to about 6; as for why it's 'roughly' 390 mana minimum, Destiny's Gift can provide +3 maximum health per cast, so for every five times you get a health bonus from Destiny's Gift you can cast Paragon 3 times, but I think the difference is more than made up by the fact that only some castings of Destiny's Gift will result in a health bonus), while Blood Curse is only available through a specific quest.