Is RioT planning on revealing new nations to rival Demacia and Noxus at any time? Or perhaps a new uncharted area of Runeterra?

Well there is all the mysterious places south of the Sablestone Mountains that little is known about, such as the mysterious Shurima Desert where Nasus and Amumu spend their time. As well as the Voodoo Lands where Annie was born. Even less is known about the jungle region of Kumungu, All we know about that is it's where Shaco and Teemo get their poison. And we know absolutely nothing about the Fyrone Flats.

don't forget the mysterious Island where some witch created fiddlesticks (annie's mum, maybe?)

Undead Icathian army.

Would be so much win.

Just about the entire Southern half of Valoran is uncharted within the world. There are some explorers who know more than others, but the entire area has been a no-man's-land since the Rune Wars. For instance, nobody really knows where Icathia is. As for uncharted areas from what we can see on the map, I can't really say anything for certain, although the Valoran map doesn't necessarily cover the whole planet...

I definitely think Icathia could give Noxus and Demacia a run for their money.

Also, even though Bandle City isn't a city-state (I believe), it's still got like 5 champions out of it. That would fall under the category of "south of the great barrier", though..

Freljord, Zaun, and Piltover all seem like they could be good city factions to throw into a mix (i.e. a 3v3v3v3 map would be NoxusvDemaciavZaunvPiltover)

Sorry, that is the exception. Bandle City is walled off from the ravaged portion of the Southern half by the Sablestone Mountains, and the yordles know a couple special routes to the Northern half.

Haha.Bandle City is cut of by the Sablestone mountains. Which in other words is the sand stone mountains (sable=sand in french). Nice play on words:P