Sounds like a great idea, you really have to post it here when it's done! :O But back to the design! (If you still need opinions) Adding totally different hair colors is a good idea, the hair plays a big part in a character (duh to me, of course you understand these...). Could highlights work for one character? They're rarely used in comic books and games, can't really remember any character with highlights that are, eh, remarkable. I also think that one way to appeal many kind of people is adding different kind of hair lengths, one short, the medium one and the last can be long. And different outfits sound good, you can make the characters more variable that way!
What art style are you using, by the way? Manga, pixel...?