This is a very interesting issue, here is my take:
I've been thinking that you could tie influence to buildings, say give a small base settlement influence radius and then have claim territory within x tiles from it's structure. You could then modify x by other factors, say local settlement density, population, distance from the colonies gravitational center, etc... in order to discourage colonies from getting spread too thin. That said, distribution inefficiencies are their own elegant solution to shoddy city design. I don't like tying territory to biome types, I think most or all of my cities would fail that check.
I would also limit how closely settlements can build to each other, requiring them to merge administratively first. With some level of separation enforced, I would then have the game automatically decide which settlement a building belongs to based on the owner of the ground it is placed on. Now you no longer select a city through the menu, you select simply by viewing it in the main game window. You're now either in creation mode or destruction mode. :D Defining territory more explicitly while managing it more abstractly could be useful later on with empires, where ownership can be multilayered and ambiguous.
Some buildings may ignore territorial ownership, instead allocating labor by raw proximity and availability. These would possibly include roads, mines, hunting/lumber camps, towers, etc. It might be useful to add a tower type distinct from the one for use with walls. This could be the same as the 2x2 planned for early game and could be useful for territorial control later. I typically have mines fairly distant from my settlements, so I'll place a tower next to them for monitoring and defense. A building that claims territory can only be placed on territory that is already owned, and a building that does not claim territory must be placed within a certain distance from owned territory.
I'm unsure of the best way to effectively limit settlement size. One could use public health factors, effective distribution limits, or food production in various ways to provide soft caps that might evolve with access to new resources and technology.
Mr. Coel has some pretty great ideas with masklings. Perhaps they could rarely take over cities or even empires, like the hyksos, the amorites, the hittites, the kassites, etc. Having desert tribes or forest tribes is also pretty compelling, along with monsters roaming the land. I would also like to be able to turn away migrants, but have them potentially form/join other local maskling camps or villages instead. Many other rich possibilities with migrants in general, to be honest, but I've already gone on too long. :P Edit: I couldn't help myself. Imagine a drought in a neighboring region prompting a large influx of refugees into your own. Now you must balance integrating them into your empire (with all the logistical troubles that brings with it in terms of food, housing, public health, happiness, etc) against them just pushing you out and taking over.