I'm still very new to Civ 5, but what about modifying the barbarian system to include a City State mechanism for the middle and late game? Empty areas of large maps would start to be filled with new city states instead of just endless barbarians with increasingly improbable weapons.
The way I would see it working is that each turn the game looks at the barbarian encampments on the map. If the encampment is at least x tiles from any city (but maybe within y tiles of some source of civilization), none of the surrounding z tiles fall into another nations borders, then the encampment may be eligible to become a new City State.
The actual chance of an encampment becoming a city state would depend on how many turns have passed since the encampment was created. There would be a minimum number of turns it must have survived, and then for each turn over the minimum the chance of founding a City State on that encampment would go up (assuming the previous distance and border conditions are still met).
As the game progresses the minimum number of turns would decrease, while the extra chance for each turn over the minimum would increase. These numbers would be tailored so that City States could first start appearing in the medieval period if the map is not well populated, and by the modern age even a short lived encampment would likely become a City State if not destroyed.
In a historical context this would represent how over time and with a easier access to the tools of civilization the 'barbarians' became less nomads with axes and more tin pot dictatorships with AK47s. We might even take this farther with a 4th type of City State that can only be founded in this manner - the "Rogue" city state. Rogue states might be more aggressive, but have a lower diplomatic penality if you attack them (I'm not sure of the benefits for being friends/allies, apart from giving you their resources and attacking everyone except you).