I like Mr. Will idea combined with Snarko.
A tribe has a 'size'. Starts at size 1. When it reaches 8 it splits, 2 size 4 tribes. Citizens 'eats' much less food than normal.
When you settle, you start working on the tiles. You cannot build tile improvements and your city radius is only 1 tile (so 8 tiles + the one under the city). However, for each turn you work on a tile, it gets a 10% chance to deplete, for example. So after 10 turns, most tiles will be depleted. Anyone else building a real city there would get a depleted tile too, it could become a negative resources like a fallout. Could be 'cleared' later on with techs by workers.
Each settled tribe could have a cultural border related to their size, which would be pretty large, to have space to move to. If not, you'll end up having no where to go real fast, unless you have no borders and can settle on square if you are at war with the civ or something, without altering their borrder... open border would be problematic, since you deplete the tiles and would prevent your friend cities to work on tiles, so you could only settle on free tiles and enemy tiles. A pacific nomadic civ would be a rarity, as you'll have to declare war some day to be able to settle on fresh tiles
When you unsettle, you start losing population each turn, so if you stay unsettled for too long, you could reduce your size considerably.
Nomadic Lifestyle could become a new civic. It would give cool bonus compared to sedentary civs(faster unit production maybe, population eats less, bonus promotions, etc.), but would limit growth in the end, including techs and all. When you become sedentary all your settled tribes are converted to cities and unsettled tribes are settled in place and converted to city. If you want to switch from sedentary to nomadic, I dunno if it's possible. If it is, you would lose all building and such... it could be realistic, but in the game, with civs expanding their borders over and over, you would have nowhere to settle on so I think the switch to sedentary would be permanent.
Each civ could start as nomadic. Agriculture and other 'sedentary techs' could be moved later on the tech tree. Until then, nomadic needs to be stronger than sedentary, but with agriculture, and subsequent 'sedentary techs', staying nomadic would become less and less interesting, unless the are you start in isn't good for agriculture.
Sedentary techs really needs to be all on an optional tech path. Nomadic civs could advance (up to a point, probably industrialization) the tech tree without needing to discover sedentary techs.
You'd probably have to change city growth too, since right now, you don't need to irrigate/build farms on every tiles to grow like in previous games, often I have a couple of high food resource and the rest of the tiles are not farms, which would reduce the impact of agriculture. Then again, the fact that you cannot build any tile improvement would be a pretty strong case toward sedentary lifestyle alone...