Funny, I was thinking of something like this.
I would suggest: commoners, warriors, experts (for regular tribesfolk), and barbarians, scouts (complete Adventurer), spirit shamans (complete divine) and warlocks (complete arcane) (for special tribesfolk, including pc heroes). No other classes.
Humans, half-elves, and half-orcs would be the only PC races. Elves would exist as NPC's not always friendly (wild elves, more CN, and with Warlock as Favored class). Fey would be a type of spirit folk. Warlock powers could come from fey or from demons. Orcs would exists as NPC's (although not as "Degraded elves" but as a race in their own right). And things would stand as a three-way battle between the tribes, with the orcs being dangerous all the time, and the elves being sometimes allys, sometimes treacherous foes. Note that wild elves and orcs both take hits in intelligence, giving the human tribe a bit of an edge there.
There should be some humanoids as well, but all would be in a primitive state. While there could be music, I am leery of the special powers of bards this early in a tribe's pre-history.
If you go greyhawk, you only need three gods: Kord, Corellon, and Grummsh. All chaotic.
Mind you, alignment might be less relevant in primitive times.
Or you could just play Dawnforge.
Anyhow, just my 2 cents, hope this helps.