I rarely take him as the first hero or use as my primary hero is be cause of my personal game style. Basically I think faster is much better than stronger. I don't even like Barbarians 14 moves and I wish I could afford to get him moves early in the game, if the map is large enough, sometimes I do.
But a lot of people take Paladin as their first hero and they do fine with him. They use leadership to back up Barbarian to reach his full potential while being able to search for ruins. Or they use him with Assasin. I have seen slow and deadly Paladin-Assasin-Catapult-Medusa-Wolfe Rider with Spiders or Elements. You may later upgrade it with Red-Devil-Archon.
Again, I am a Paladin user and I never get to a point of complain be cause of him maxing out. I just think his slow and I don't take him first.
When we were playing Warlords early version before teleport, almost everybody had some version of Thief-Ranger-Shaman-Priest. Thief Ranger providing speed and Shaman-Priest providing power spell. With Teleport came the variety. Still Wizard, Summoner and Alchemist became primary heroes (the hero you want to start with and want to level up) and while the others became secondary. With KGB's K4 patch and Stormheim Units it changed again. But there are always primary heroes and secondary heroes.
So my point is, it is not a shame to be a secondary hero.