A single deity AI is a pain but can be beaten. I like the concept of going after the cities. You will have a hard time with this until you get an army to hide your attack force under.
Since I have never played a one on one like that I can't say the best way to go about it, but I would think a good settler factory and land grab is top priority. The AI will get ahead in tech but the lightning spped they get from trading won't be there. Once the land grab is over get your defenses together and get to war.
Since the AI can outproduce you, it is important to watch the ratio of units you take vs units you lose. I think the AI gets like a 60% discount (spearman costs 8 shields not 20). For 100 shields you can build 5 archers or spears, the AI can build 12.5. This means you will need to wipe out almost three of theirs for every one of your that is lost. Really 4 to 1 is probably safer so you can slip some other improvements in between.
How do you do this? Well you have to maximize opportunities. The AI should never get to attack you immortals. Put a spearman on top to defend since he is cheaper. Always travel in stacks with some archers in there. As you know archers can strike first on an enemy attacker, taking off a hitpoint - this helps tip the odds. Get your units on a mountain, hill or in a forest. Get fortified up there when you know they are coming. Find natural ways to force attackers into grassland before attacking them. Use the combat calculator and figure out if you are better off attacking or defending. If you can configure your border so they have to approach your walled city on a hill from grasslands, you have an advantage. You are going to face big stacks outside your city walls, don't panic, and don't worry about clearing the last one in the stack. If your troops sit outside the wall, they will get picked off on the IBT (you could keep a horsemen or other 2 move unit for this). Of course you also want artillery since it fires when they attack and when you attack.
You will probably want to be in war most of the time to keep them from getting a big surge in units. If you can overcome the initial surge then the rest is manageable. If the wars start before they get all their roads up then it will keep them from getting that giant surge where you get completely overrun.
I played a succession game at deity where we got down to us (India) and the AI (Persia). It was a little late in the game when this happened since there were many AI at the start. Persia really was running away with it. They had almost 50 cities and we had 5 IIRC. You can read the whole SG story its in the civ index link in my sig - or at this link:
http://forums.civfanatics.com/showthread.php?t=153707, you could read it all or start around page 13