One way to avoid the inevitable difference between veterans and newbies might be to make heroes such that rather than having a specific level, they had a maximum level.
A hero's maximum level would be two levels beyond the highest (max)leveled hero in your opponent's deck, with a deck lacking a hero only allowing a level 2 hero (i.e. no hero counts as L0).
If the hero still had to pay a "training cost" (i.e. the upgrade fee), and the upgraded abilities weren't too major for each increment, then the idea probably could have merit, though. It would certainly be fun.
I suspect the coding work to implement the idea might be a touch hard though...