Changing teams in game has been proposed before, I know, but I would like to add a new element.
First of all there should be the possibility of having multiple "game modes".
These could include "Treaties", "Locked Teams" and others like "Kings" (kill the enemy king) or "Capture the Flag" (take the enemy flag and bring it to your flag, "Battlefield" (two armies fight against each other, no buildings), "Settlers" (multiple flags on map, place a building at each flag to win), "Wonders" (build a wonder), "Favour of the king" (would require trade carts, bring carts of gold to the kings castle, the first one to convert the king to their team wins) etc...
Most of these are more scenarios but I'll put them in the right order them later.
Treaties:
A new building could be added, some kind of diplomatic building where you can ask for a peace treaty with one of the other teams, you may have to pay a certain prize for it (resources, or even troups and buildings). You can bribe players, betray players (giving their armies location to the enemy) and do many more things.