What about a special "king" hero. This hero could only be taken as your first hero in a game. The king would actually be a sub-par hero. His stack-boosting skill could be defensive leadership (20 points for 5)... or he could have city leadership (making him vulnerable in open battles). His movement would be quite low (he travels with his court), and his undead lore would be pathetic.
The king would have some perks though. He would have some skills that give a you a global boost. One idea would be to give him a skill to increase your income by x% (rulership). Another would be to give him a % reduction in the cost of hero offers (glory). Another would be a % reduction in the cost of city walls and new unit production (builder). Finally, he could give a global morale bonus to all your units (inspiration). I would keep the effects of these skills quite small, but with many levels the king could give an appreciable global bonus.
So, he's a terrible starting hero. He has some potential, but leveling him up will be a pain. You might be wondering "why would I ever take this king?" The answer is ladder points. By taking the king as your first hero, you are saying that you believe you can defeat your enemy with a handicap . If your king survives until the end of the game, you get some extra ladder points. In non-ladder games the king would not be available (unless you were playing with the 'regicide' victory condition).
In regicide games, you must start with a king. Losing your king loses you the game and your remaining cities revert to neutral control.