I don't play 4Ed, so I'm couching my suggestions in 3.XEd terminology.
1) Without written language, Wizards (if they exist) would need alternative methods of codifying their spells- etched stones, strands of knots (with or without beads of stone, bone & shell), or even tattoos would be appropriate.
The Sorcerer- probably the Battle sorcerer- would be the most common full arcane caster, if any exist.
The Bard in some form, would be the most common arcane caster of all, unless you use the Kingdom of Kalamar Spellsinger.
2) With animism being the main kind of theological view, the shaman should probably be the default divine caster. Another option would include the totemist from Magic of Incarnum.
3) You're going to want to have some kind of weapon breakage rules.
4) The totemic barbarian- see Unearthed Arcana or, better yet, Arcana Unearthed/Evolved- would be great for this setting.
5) The Rogue should be replaced by the Scout.
6) No "Mounted" anything feats.
7) You might want to include the Neandertals from Frostburn.
8) No Monks, Paladins or anything requiring a high level of training/discipline/asceticsim.
9) Don't forget the atlatl, the bola, throwing axe, the javelin and shortspear, the throwing club/boomerangs, and slings would be your main ranged weapons. (See
Primitive Hunting & Fishing Techniques)
10) Some cultures had some truly unique and brutal weapons- I always loved the shark-toothed sword-clubs of the islanders in the Pacific and Indian Oceans.
11) I would drop Simple/Martial/Exotic. Some of the tribal weapons out there would be considered Exotic in a typical D&D game.
I would have Tribal/Exotic weapons instead- anything your tribe doesn't use is Exotic.
12) Language is going to be a tough one. "Sign Language" would be about as close to "Common" as it gets.