Well, playing on a Large or Huge map increases the map size disproportionately to the number of civs. That is to say, even though 12 civs is 50% more than 8 civs, the huge map is nearly 150% larger than the standard map (128x80 vs. 80x52). Assuming the land is distributed equally, this gives each player 64% more room to expand. Of course, on Deity, it probably won't be distributed equally. But in my experience with huge maps, and given that you're fairly experienced yourself, I don't think it'd be too hard to get to 6 cities with Liberty.
Be forewarned though that the AI also gets that much more room to expand. So if you're thinking to go from 4 cities to 6 cities, then expect the AI to go from 6 cities to 15 cities, and the per-city science penalty for that is reduced from like 5% to I think 2%. But that should at least make Liberty viable. Almost mandatory, even. I tried the standard 4-city tradition as the Inca, had good growth thanks to a number of high-food terrace farms, expanded to a 5th but way too late (Renaissance or maybe even Industrial), and lost a science race by just a few turns to Gustavus Adolphus who had acquired some 25 cities or so through warfare.