Although there is a hacked .exe (for both the game and the editor, IIRC) floating around on CFC, which allegedly increases the city-limit, no-one (except the original creator) seems to have got it to work as intended. From what I've read, it tends to cause the game to crash irretrievably after ~560 towns have been placed (the AI also won't build towns exceeding the 512-limit itself).
So basically, you just have to deal with it — at least if you want to play an epic-type game where you build your Civ up from nothing. The hacked Editor can be used to preplace >512 towns on a Scenario map, but you would then (also) need to play using a 'NoRaze' .exe, to stop the AI from destroying 'excess' towns.
But 512 cities can still cover a pretty big map: if each city gets ~20 exclusive tiles, that's ~10240 tiles, so (assuming all are land-tiles, which they won't be) on a 70% water map, that's ~34133 tiles in total, or ~185 x 185. The biggest map that the Firaxis Editor can make (AFAIK) is 256 x 256 — but due to the offset/isometric layout, that's really only 256 x 128 = 32768 tiles. So your 512 cities would easily fill that world, especially if you make additional terrain-types non-Settleable.