Okay, I finally sat down and wrote out info on Shai's tribe in the new 4e setting, which I think fits well with how / why they got rid of him. Lemme know if it jibes for you and I'll add it to his Character post:
The Northern Barbarian Wastes are known for their harsh climates and harsher living. The tribes survive on weeding the weak from the strong. Ritual combat chooses each tribe's leaders, and annual challenges between the tribes establish the region's power structure. It's a tradition spanning back as far as they remember, and assuring that only the hardiest stock leads and produces the next generation.
At least, that's the story.
Certainly the power structure of the region is established by strength, but the Tchant'cos Mer, ruling tribe for generations, uses a strength for which their brethren have yet to find a counter: commerce.
Once they were no more than a nomadic scouting people scoffed at for not having the power to conquer and hold their own land. But while they couldn't stalk down a bear with only a hunting knife, they were especially good at laying traps. And eventually they laid those traps along the only trails out of the northern peninsula and into the more resource-rich southern lands.
Now only Tchant'cos Mer tribesman can safely traverse the trade routes south, and with their increased power and influence, soon all trade routes in the northern peninsula fell under their control, as well. It's become impossible for the brute tribes who previously lead to survive without the help of their 'lesser' kin.
So the ritual combat and annual challenges continue, and there's even an uncertainty to where many tribes will fall in the hierarchy. But the Tchan'cos Mer champion is always from the family with the greatest trade influence in his own tribe, and no one in the other tribes dares topple a Tchan'cos Mer champion.
