Really, Europe is crowded enough and some small civs should be removed from it (ex. Poland, Netherlands), but I know, at least, Poland was discussed and shot down.
I do think Africa and North America could do with a few more civilizations. Africa could have three more, a generic Swahili civ, Zimbabwe, and South Africa.
Swahili
Spawn - 900
Capital - Kilwa
Leader(s) - Ali ibn al-Hassan
UP: +2 gold from each trade route in your city.
UB: Port - Replaces harbor. extra gold from trade routes.
UU: Dhow - Replaces trireme. Extra strength and can travel through capes.
UHV: Connect 3 fish and 3 whales by 1050, Have 1000 gold by 1100, Make 1000 gold from trade with other civs by 1500.
Zimbabwe
Spawn - 1000
Capital - Great Zimbabwe, Cape Town (1900 after possible respawn)
Leader(s) - ???, Shaka (1790), Nelson Mandela (1990)
UP: Defensive buildings provide +2 food.
UB: ----
UU: Impi
UHV: Have the largest city in the world by 1500 (GZ was the largest city in sub Saharan Africa), Ensure no colonies in Southern Africa by 1950 (Represent the Zulu), Something to represent South Africa.
Respawn: South Africa after ~1900
Reason for inclusion of Zimbabwe and Swahili. Archaeological evidence suggests that Great Zimbabwe became a centre for trading, with artefacts suggesting that the city formed part of a trade network linked to Kilwa and extending as far as China.
And even though I know Leoreth always shoot down these next suggestions, I'm suggesting them anyway.
Mississippians
Spawn - 800
Capital - Cahokia
Leader(s) - Tuskaloosa, John Ross (1800)
UA: Rivers act as roads (extra speed for units).
UB: Mound: Replaces monument. Does not go obsolete and extra culture.
UU: Blowdart Man: Replaces archer. Extra combat strength agaisnt barbarians.
UHV: Have the largest city in the world by 1300 (it was comparable to London and Paris in size, though smaller than Cordoba, Baghdad, etc, but have one of the largest cities wouldn't be as hard!), Enter the Medieval era before meeting an old world civ, Ensure no European colonies in North America east of the Mississippi by 1750.
Respawn: Cherokee ~1600 (the Five Civilized Tribes are descended from the Mississippians)
Pueblo
Spawn - 200
Capital - Mesa Verde
Leader(s) - Po'pay
UA: Desert and mountains provide +1 food.
UB: Kiva. Replaces Pagan Temple. Extra culture and happiness.
UU: ???. Replaces Spearman. Weaker attacking, but extra defense. (Referring to the Pueblo Revolt)
UHV: Own the Rockie Mountains by 1400, Have no city convert to an old world religion by 1700 (once again, referring to the Pueblo Revolt), Ensure no European colonies in the Rockies, California, and Mesoamerica by 1750.
Reason for including the Mississippians and Puebloans. First, it would make the Aztec and Mayan games a bit more interesting to play before the Europeans show up. Secondly, there is
some small evidence of trade between Mesoamerica and the Anasazi. Finally, some scholars that believe migrations and trade between the Mississippian natives and the Mesoamerican civilizations
spawned the Mississippian civilization.