Okay, my list of Legit Formable Nations reworked (few most pointless/disliked states less)
FORMABLE NATONS
1) Belgium - historically existed in 1790
http://goo.gl/rnCf6
2) Yuan - historically existed till 14th century, possible to form again by Oirat/Mongols when conquering China. No idea about NIs.
3) Arabia - ya know, united Arabian Peninsula. Historically was united as 'Arabia' in early 20th century (hey it's 'just' one century after the end of EU4

Earlier than Hindustan...) Still Arabian NIs.
4) Al - Andalus - possible to form by Granada or countries from Maghreb region after (re)conquering Iberian Peninsula. Historically was precedessor to the Emirate of Granada. Adopts Granada/Berber NIs, depending on country forming.
5) Myanmar - in the Art of War this area will be divided on many smaller states so unificating them should be possible. Why 'Myanmar' instead of 'Burma'?
http://goo.gl/BqfFv Adopts Taungoo NIs.
6) Siam - possible to form by Ayyuthaia (or any different Thai country). Forming Siam includes adopting Absolute Monarchy, Ayyuthaian NIs, bonus towards Western tech.
7) Kurdistan - new culture in the Middle East. Possible to appear through rebellion/event (not sure if AOW will have some Kurdish small state, if yes - forming Kurdistan should be possible via it). Unique NIs.
8) Maghreb - Morocco + Fez + Algiers + Tunisia. Historically existed as Almoravid Empire but Almoravid is the name of past (extinct) dynasty. Still Berber NIs.
9) Durrani - possible to form by Afghanistan/Afghan countries if they control Afganistan + Pakistan + Nishapur. Unique NIs.
10) Srivivaya - possible to form by Aceh if Srivivaya dynasty still exists. Requires owning Sumatra and Peninsular Malaya. Allows on conversion to Buddhism. Still Malay NIs.
11) Vietnam - requires being Dai Viet and owning provinces of Champa + these 1-2 provinces of Khmer which exist today as southern ('Nam') part of country.
12) Somalia - Adal + Ajuraan (essentially, Somali countries).
13) Missisipi - Native American Empire constisting of provinces of 9 tribes close to Missisipi River: Cree, Chocksaw, Cherokee, Osage, Caddo, Pawnee, Susquehannock, Miami. Capital in Cahokia. As much ahistorical as Hindustan.
14) Turkey - possible to form by Beylik countries owning all Turkey area if Ottoman Empire doesn't exist, or by OE if it doesn't have European provinces besides Constantinople but has all Turkey. Or something like that.
15) Ghana Empire - possible to form by Macina or Jenne (AOW Western Africa). Unique NIs.
16) Hausa - possible to form by any of Hausa state owning all Hausa culture provinces. Unique NIs.
17) Illyria - proposed by some people instead of Yugoslavia. I guess it should be formable by Croatia/Bosnia/Montenegro/Serbia/Albania if a country owns all other mentioned states. Unique NIs.
18) Europe - wait! Of course it is ahistorical! I simply think it should be a sexy option for countries dominating European continent, so it would look lovely to see 'Europe' instead of for example absurdly big 'Alsace'
RESTORED EMPIRES
Mongol Empire - possible to form via Hordes uniting, well, Hordes from Kazakhstan to Manchu.
The Caliphate - the result of 'Unify Islam' decision.
Majapahit Empire - Majapahit in 1444 starts as small Javanese nation, the remnant of greatest Indonesian empire ever (from medieval era). Restoring it would be nice. Unique NIs. Alternate names: Indonesia, Nusantara.
Khmer Empire - possible to restore by Khmer if they control Cambodia, Thailand and Laos.
Celestial Empire - what I am talking about in this case is non - Ming Chinese nation (Zhou, Shun, Xi) restoring unique 'Celestial Empire' government after owning all Han + Cantonese provinces, not sure if it is already possible in game.
NEW COLONIAL STATES
Australia
Philippines
South Africa
California
Bonus: a bunch of completely crazy completely ahistorical ideas just for fun.
Celticia - Ireland, Scotland, Wales, Cornwall, Brittany.
North Sea Empire - Denmark, Norway, England, Scotland
Balkania - Yugoslavia + Bulgaria + Romania
Great Finland - Finland + Karelia + Ingria
as - Sudan - Western Africa united
Dravida - souther Indian cultural union
Transoxania - Uzbek-Turkem-Taji-Kyrgyz-Kazakh-stans 
Interior - Native North American union of all Western tribes
Gallia - France... with Animist religion

Assyrian Empire - Syria + conquering hella lot of Middle East
Caucasus - all Caucasian cultures united