I just found out there is a maximum of 22 civs on a map

So no Polynesian civ, unless I throw another one out. But thanks for the suggestions! I will just add Tonga as a city state.
Did a few tests increasing the evaluation range of settlers, but to no avail. The best I got in my runs (300 turns, until 1860) was a Persian city in New Guinea, a Carthaginian one in North America and an Arabian city in South America. Pretty poor still. The side effect were some far-flung continental expansions.
A future fix may be some scripting; e.g., the first 5 civs to reach the new world get a free settler there. Then, new settlers appear at the initial settlement (at the cost of population in the homeland) depending on factors like population size, happiness, naval power, ... Far future work.
So what is next: I will include the "not another city states" mod (good tip Lachlan!), which adds more types. I will then also add more city states: Dublin (as England mostly fails to found it), Karelia (I don't want any Germans or such there), Awdaghost, Tblisi (I enlarged the region; good pick KaiserKevin!), Aksu (in Xinjiang), Yakutsk, Sri Lanka (India has enough space), Uluru (Ayer's Rock) and Tonga. This will bring the total to 30. I also consider including the "better city state diplomacy" mod.