This may be a bit of an open door, but raids, defenses, trade and migration should be a thing.
Raids could be really simple, tribes can start wars, and when at war tribesmen can attack other tribesmen (perhaps even tamed animals), steal resources, and maybe even destroy structures(except for the structures, I am describing war during the tribal stage in Spore, now that I think about it).
Trade could work similar to the civilization franchise; there’s an UI wich displays what both sides have to offer, you can select what you want to give them and what you want them to give you, and once you have a deal the AI (or another player) agrees with, you can click ‘accept deal’. Once you click, a few tribesmen will start carrying the traded goods over, possibly accompanied by a few warriors as escort.
Maybe gold will be unlocked somewhere in the game, wich allows fair trading, even though the other party doesn’t have anything you’re interested in.
Migrating with the whole tribe is already possible in the current game (for as far as I know), you can just abandon your stuff, order your people to walk somewhere else (perhaps carrying resources) and settle down somewhere else.
But what I mean by migration is lone people (or even people of other tribes) can join up with other tribes.