So, it sounds like we could simply have AI neutral nations that exist as basically AI players. They might not have all the powers of a player (maybe not cast spells as a wizard) but would still advance cities, create settlers, and have diplomatic negotions. They wouldn't be as powerful as a real player, but would still be a factor.
I think that if a community of neutral cities are left alone for a long time (I know in my MoM games, there are often many towns connected by roads that arn't touched until late game) they should band together as a new player.
I am sometimes annoyed in games like "Sins of a Solar Empire" when online players thumb their noses at the idea of having AI players. Like the precence of AI players that you can ally with suddently makes it a comp-stomp or something.
I think there should be neutral slots that can only be filled by AI players that would be specifically placed on the map in such a way that they give an edge to those who try to use them as an ally. You should have it set so you can lock teams that only locks the player teams with each other (so players cannot back stab each other) but still allows for missions and teaming with the AI players. I think that would make the neutral AI controlled players much more interesting. Also, in a FFA game, one player might not just rampage through the neutral towns because he'd rather be the better ally and trick the AI to go attack his enemies.