A solution Stardock could implement is that after you receive the L9 choice (400), any heroes after come from the whole available pool, and get extra levels that would be added like when a Henchmen starts at a higher level (ie. no bonus XP - just complete extra levels). So at 800/1600/3200/6400 fame milestones (which are all the ones programmed and probably all you'd ever need in one map) you could level up a hero from the predesigned level up to L12/L16/L21/L27 respectively. This would make lower level choices a more attractive option, as although you won't get equipment that is as good, you get to custom level your champ from their current level to the higher level. So you would weigh up the starting skills, and choose the one you like the most and then level them up.
See my suggestion to Stardock here: