I'm playing as the Songhai, and I'm the only civ. Every city that the minor civs have founded has been an unused Songhai city name. My guess is that they're just pulling from a bank of unused city names for any civ in the game, which in practice will probably work just fine.
After 350 turns, they've long since used up the last Songhai city name, and have stopped founding cities despite having a halfway decent amount of unclaimed land available. I should also note that none of the city names have been duplicated.
So, basically, it looks like the Firaxis team has already done a lot of the hard work here. City-states don't do stupid things like try to use the same names over an over, and it doesn't cause the game to crash or anything when they run out of city names - they just stop building cities. Works for me!