ok, here's an idea that incorporates many of the aspects that you seem to be wanting, although some of them i cant wrap my head around unless you are playing a scenario with a set map and then it would be a slightly easier matter to simply hardcode them into the scenario... anyhow...
data structures...
instead of listing the cities by civs, they are consolidated into one big list, classified into categories, and then sorted by distance from capitol and flagged with the relevant civilizations and assigned a percentage, pseudonyms, and whether they are on the same continent as capitol or not)
For instance ~
Boston - American (Boston, 100,mainland), England (Bostonia, 10,overseas)
this would mean if the city has not been created, the americans will name their next city Boston 100% of the time if its on the same continent as their capitol. the english would create the city of Bostonia 10% of the time if its not on the same continent as their capitol, or rename Boston to Bostonia if captured. (not historically accurate, but I needed an example). If this name isnt chosen or suitable, it will continue moving down the list until it finds one that IS suitable and not in use.
But this isnt the half of it. Since we're trying to be accurate here...
Lets sort them into separate lists... not by civilization, but by terrain.
To start simple, I'll keep the idea lists limited to...
Inland ~ (no water squares in city limits)
Coastal ~ (Adjacent to at least one water square)
Near Coast ~ (Water Square in city limits, but not directly adjacent)
Island/Peninsula ~ (majority of water squares in city limits)
other possibilites include ~
Highlands ~ (majority of squares are mountains/hills)
Woodlands ~ (jungle/forest)
Polar and Desert and any mod-specific terrains you can think of.
So basically... when a city is created... it will be assigned a name from the game by default... doesnt matter what it is... because it will IMMEDIATELY be renamed...
the script will first find the civilization that created the city, whether the city is on the same continent as that civ's capitol, whether its adjacent to water, and whether any terrain in city limits has a majority.
If its adjacent to water, it will start at the top of the "Coastal" list, and work down until it finds a city possible for that civilization, and check to see if it is the same overseas/mainland status... if not, it will move on. If it is, it will roll the % to see if the name is chosen. (this is important since some cities may be important for some civilizations, but not for others... such as the boston example). If the city isnt chosen, it continues until one is. IF the end of the list is reached without ANY cities being selected then it starts from the beginning again, and simply takes the first city open to the civ. If NO cities are left for the civ, then it will start over AGAIN and simply take the first free city. If none are found at this point... then I dunno... I guess it could use the default citynames which can be set to some generic junk unused in the lists.
When a city is CAPTURED, it will simply find the city in the list, and see if there is a pseudonym assigned for the city capturing it. If there is, it will be renamed. If there isnt, it will remain the same.
Hopefully this concept is diverse enough for your needs but feasible enough to be coded in. To keep things simple, I didnt @!#$ with the initial coding at all, but it could hopefully be done in a manner entirely separate from the existing mechanics.