The easiest way is to just place some altars at the player's start location, and have the player buy a hero of their choice at the altar.
An alternative way is to place a bunch of heros on the map with circles of power near them, and give each player a 'chooser unit'. When the chooser unit moves onto a circle of power, that player gets to use the hero associated with that circle.
Ghan has said he has fixed this. Monovertex please confirm this fix. This was only a problem with people that had signatures in the upper levels like not the special members but the respected members.