I think a weaker version of Natars would be good.
Maby named Exiles.
The other idea i have is China.
They would have pretty strong and expencive units like Romans, but their first unit would be Peasants. Peasants would be weaker and cheaper than clubswingers, but also quicker to train (stats maby around 30, 20, 15). And the tribes special building would be something that would make the Peasants more usefull (maby make them produce some resources or boost their strength). And the hero bonus would somehow affect the units (maby slightly increase their atk and def(5% for Peasants and 2,5% for other units).
Well these are just the ideas i quickly came up. I think i could make them more precise if I took some time to think about game balance.