I think that cyberpunk literature might have a clue here as to how this might happen.

1) Decouple states from strictly adjacent geography. There's no reason that "France" has to all be where it is in Europe. We already have precedent for that with Embassies, Diplomatic vehicles and other foreign soil recognitions. Imagine a France franchise the size of your average McDonalds, in the middle of what we now call Thailand. Maybe it's in a mall next to a Venezuelan franchise. You can pass between entirely different governing systems as easily as walking between stores. There's other precedents, colonial territories and other overseas holdings, but those have different semantics I think than overseas diplomatic mission franchises.

2) Since states no longer are tied to specific contiguous geographic areas, why do historic nations only get to play in the franchise game? How about independent state franchises? What if Google opened some brick and mortar micro nations in city centers all over the world? Or Green Peace? Or any group of like-minded individuals able to "buy-in" to whatever threshold is required to achieve some kind of global state franchise recognition? What if stepping into any Walmart was effectively the same as walking into the Nation of Walmart? Why does a nation even need territory? What about on-line nation states?

There's some precedent here as well, with a couple non-territory owning states like the Knights of St. John having many functions and obligations of a state, without having any territory.

3) This effectively makes the (dys)topia of nation-companies come true. But it also enables very free movement between nations. Don't like how Walmart taxes the little guy? Move over to Sony, or France, or the Reconstituted U.S.S.R. in Australia.

The other path is of course a kind of global citizenship, where citizenship to individual nation states either doesn't exist or is purely optional. Or another model where citizenship can happen at different scales such as county citizenship that gives you specific rights within a tiny territory or continental citizenship that spans across nation states. Another path might be buying certain pieces and parts of different citizenships: I want American-style free speech and libel laws, but U.K. style health care and Korean style justice system...so I become fractional citizen of those three states for those things and pay taxes (dues) into those systems apportioned to some asking price.

Ultimately the real question here that will determine the mechanics of this evolution will be "what's the goal?". If it's free movement between territories, a system like the E.U. or the U.S. seems to work pretty well for that. If it's looking for a specific kind of representation (better health care in this place vs. that, different legal standards for property ownership, etc.) then some other system. Nation State membership today works because it's at some equilibrium that provides some measure of rights and obligations that more or less works for the population.

That equilibrium in many cases has changed significantly over time, with new rights being recognized, and new obligations also being asked of the citizenry, sometimes states that aren't working are dissolved and sometimes new ones take their place. But the general direction is that states with an internal ability to peacefully move along with that equilibrium seem to be doing well, and ones that provide too rigid of a framework finds themselves in trouble. The unfairness of course comes with the minority of people in each nation who are at the ends of the various internal socio-political spectrums in each state who can't get a representation-responsibility mix that works for them, and their particular state can't offer.