Just to add to this discussion, it appears from the game files that civs have city lists independent of the leaders. For example, the top listed city for Germany is Berlin, Frederick's capital of Aachen is listed 4th, while Mecca is listed as first for Arabia, with Cairo second.
The error handling for multiples of the same City State spawning is pretty funny too. Too many Amsterdam's? Don't worry, here's 'Amsterdam 1', 'Amsterdam 2' and 'Amsterdam 3'!
If the Barbarians spawn with a city somehow, it appears they get something called 'Grokville 1'.
Whilst already known as well, it is confirmed that leaders are each given a specific capital.