I'm gonna assume it's for melee. Here is my random melee idea for a new class in each race.
Something construct/engineer related. They don't necessarily fight as strong as others, but they help in different ways relating to buildings. You have an infinite amount of ways to take this hero.
They boost economy, food, upgrade speed, build speed, train speed, make items in your shop better, allow faster res time in altar or gives your altar the quick res ability. Low tax rates. Increase lumber/mine speed.
Allow buildings to produce two of a unit at once. Abilities that make the items in shops better. Repair faster.
Maybe Humans have a Bloodelf Engineer has "scout tower" spell.
Maybe Undead's guy can place blight "tumors" like a zerg queen from sc2.
Night Elf's can restore moon well mana.
Orc's have a "tower level up" ability boosting Orc burrows or towers to be more effective. (producing more food/attacking faster)
Anyway. That's the direction I'd go for a small, big change.