The simplest approach to this is to make a building, which you can't build and manually add it to all starting cities. Next you set all buildable stuff (buildings, wonders, units etc) to require this building. If you found a new city, it will lack this special building, meaning while it has a construction queue, it won't have anything to add to the queue. The benefit of this approach is that it can be done in xml only.
Next question is about graphics. One obvious solution would be to make two art styles, one for cities and one for camps. However...
PHP:
ArtStyleTypes CvCity::getArtStyleType() const
{
return GET_PLAYER(getOwnerINLINE()).getArtStyleType();
}
Each city will use the art style of the owner and to change that you need to mod the DLL itself. It's impossible to change from python. In other words you either need DLL changes or you can forget about the art style approach.
The only other approach I can think of is to add one or more buildings to the cities and make those buildings display the difference. I will not rule out that there are other ways to hack graphical differences into the city graphics but I can't think of anything.