Your entire life has been as a fish in an ocean, so you don't know a word for "wet" or "dry".
The modern nation state is, well, modern. It is a recent innovation. A blink of an eye ago, personal loyalty to a crown was the closest thing you had to it.
Immigration restrictions where even more recent than that in most of the world. People where relatively free to move into your area; if they where unable to support themselves and proved a nuisance, the locals could just kick them out or kill them (I'd say "the local police", but police are also a recent invention).
Much of what you presume is inevitable is just an accident of history, where some area comes up with a social pattern that other areas duplicate.
Right now, there are four large empires -- India, Europe, China and the USA -- which are each as large economically and population-wise as the world was not that long ago, and a number of smaller (economically or population wise) polities. Within them, to a greater or lesser extent, you have free movement of people.
With modern transportation technology, completely free movement of people would lead to significant migration. Typically, migration grows when wealth per person becomes a large multiple, and in our world there are areas that are 100x poorer than others.
In the last 20 years we have begun to eliminate absolute poverty. There are now fewer absolutely poor (using many measures; Y2K 1$ USD@PPP a day is an example of one) in the world right now than we have lifted out of poverty in the last 20 years.
Assuming the various crisis (fall of the Western British Empire, climate change, MAD, etc) going on don't derail the efforts, it is plausible that absolute poverty becomes a small problem within decades, and the global middle class swells to the point that huge chunks of the world can open up free migration without overwealming immigration flows occurring.
It becomes plausible that 60%+ of the world becomes a free-movement zone. The remaining parts will probably form imitation free-movement zones of smaller size, as politicians are nothing if not copy cats.
TL;DR much of the world is already there, just the bubbles are not connected. Having a free movement North America is quite plausible, then linking North America to Europe, and from there to the entire former USSR and East Asian democracies would be doable even without a significant economic upheaval (and would be an example of how the Western British Empire could delay its fall). The resulting political block would have the highest population, military might, and economic strength on the planet. (1.7+ billion people, 50+ trillion GDP 50+ million km^2 area)
(This is over 1/5 of the world's population, 1/3 of the world's land area, and 1/2 of the world's GDP).
Then other pieces of the world would seek to mimic it.