Here's my list of Civilizations that have never appeared in the Civ series up to now: (discounting mods-of course)
Civ name followed by - potential best victory type
1 LYDIA - commerce/culture/domination
2 KHAZARIA - domination/religion/trade
3 CRIMEAN KHANATE - domination/religion/trade
4 MEDIA (Medes/Median-Medean Empire) - culture/military/craftsmanship-art
5 ELAM - culture/religion
6 ARMENIA (classical-ancient state of Armenia was a major power in the Near East) - Trade/Religion/Highland bonus
7 TIBET - very original due to potential not only hill tile bonuses, but mountains as well ( and was a free state, a quite large one, in late classic/early medieval era) religion,culture, hill/mountain bonus
8 BULGARIA - long history, from warlike nomadic people to a powerful (Slavic) empire in the Balkans. - military/religion/culture
9 THRACIA (Thrace) - we know of only of few leaders and cities (Seuthopolis-capital) as they were more of a collection of tribes than a unified country, however, longtime rivals of ancient Greeks would be great to have in the game.
10. ISRAEL (Judah, Judea, Hebrews) religion/culture/commerce-trade
11 PHOENICIA - Maritime/Trade-Commerce/Science and Culture would apply
12 BURMA - religion/isolationist/militarist and culture
13 MUGHALS - domination/religion/trade-commerce
14 TIMURID empire (gurkani) - domination/conquest/religion/trade
15 ASHANTI (Ghana) - culture, trade, military-or religion
16 PRUSSIA - was an independent, centralized country, separate from Germany and a major European military power for centuries - domination-heavy militarist, also great in science & culture
17 GOTHS (not sure of the formal name) - Celts were featured in Civ since Civ 2, Goths were just as accomplished, if not more (conquered Rome, created states/countries) - domination/conquest, culture
18 ETRUSCANS - great culture, scientific and quite militaristic
19 MINOANS - fascinating culture, also religious, merchants and a Naval power
20 SARMATIANS - I mean, Female (virgin) warriors on horseback! you want more females in the game, right Firaxis? Then why not finally give us Female Military Units? Especially that they did, in fact, exist, fight and die alongside their male (Sarmatian) warriors. And, no, Sarmatian/Sauromatian, isn't the same as Scythian. Domination/Reiligion/Culture
21 HUNGARY - it's about time, really
22 ITALY - as an actual entity, not only Venice, just like with the Hungarians, but even more so, come on Firaxis... culture/religion/art-craftsmanship/militaristic
23 WENDS - The now gone Wends were western Slavs who lived in the lands of the former East Germany, along Baltic Coast and inland, from Oder/Odra river up to Labe/Laba river in the west. Fascinating culture. Similar to Celts: Militaristic, Religious and Agrarian
24. SAXONS - militaristic/domination/religious
25 NORMANDY - for William the Conqueror, yes, he came from France
26 GAUL - militarist/religious/culture-agrarian
27 BRITONS/WELSH just like Gauls of France and Northern Italy, however, with separate Leaders and Uniques (and language/dialects)
28 FRANKIA - call it that (Franks-Frankish empire isn't really formal-proper) ,give them the capital of Aachen - their proper capital, and Charlemagne as Leader.
29 DACIA/WALACHIA/ROMANIA - worthy addition
30 SWITZERLAND - Neutral! also, strong culture/science and mountain/hill bonus
31 SHAWNEE - Tecumseh formed a strong confederacy, dreamed of a Native American Empire, a country like the European model.
32 APACHE - warlike/desert bonus - Geronimo as leader
33 CHEROKEE - best known of the Five Civilized Tribes
34 INUIT - tundra and ice tile bonuses
35 TOLTECS (or perhaps OLMECS) for culture and religion
36 UKRAINE/KIYEVAN RUS - culture/religion/military
Wanted to go on till I reach 50 but real life calls, well, anyway, there it is for now.