I feel you, brother. I had gotten really close, but beaten in the endgame in the space race, beaten in the endgame by a cultural victor, beaten in the endgame by my former allies all turning on me at the least second...you get the picture, I'm sure. It finally all came together for me this morning, when I beat Deity (Normal/Continents) with Nubia (random leader). This turned out to be the lucky charm, and it crystallized a bunch of Deity-only thinking.
I think the most important aspect of Deity games is that you have very little margin. A barb camp that somehow spawns a swordsman can be enough to ruin your whole game, let alone getting caught in a war of attrition. All the micro-ing city location doesn't matter when you get wiped off the map before turn 100. Falling too far behind in culture, or tech, or (sometimes) religion can be unrecoverable. This means you need to be quite hardcore, and know when to quit. I'm not generally a big restart spammer, but in deity, it too much of your initial grid is unproductive mountains you'll never live long enough to compensate. You better be happy with your start to have a chance.
Working strategy really has to counter the insane 3 to 1 advantage that Civ gave Deity AI. For most of the first hundred or so turns, you will be fighting AIs with 2 or 3 times the number of cities. Even if you go weapons heavy, you simply don't have the productivity to look like a threat, which makes it highly likely that you'll face an early surprise war, even with just opportunistic AIs, never mind aggressive ones. You should have a plan for how you not just fight off that attack, but to counterattack and take at least one city. This will go a long way in discouraging continuous "you weakling" wars, and gooses your productivity with a somewhat developed city without burning the resources (and time!) for it.
Things that will help survive that war? First, expecting it and being ready to pivot from exploring/developing to battle. You can't fix it the easy way by just building lots of military. In this early game you have GOT to get more cities going asap to minimize the headstart the AIs get from their 3 settler starts. No matter what the leader, Archery is going to be critical, since you'll be heavily outnumbered and need to win while taking little to no damage. Leaders that have powerful early game UUs can be critical in helping you survive this first onslaught. Even with some help from your leader, you need to be extremely picky about how you fight. No head on attacks, preferably just you using ranged weapons with your limited units fighting from with the city or at least from squares with big defense bonuses and heavy movement penalties. You want to force to always get the first attack by staying just beyond the movement range of the attackers. Most of your attacks should be ranged weapons only, melee units should fortify and absorb damage except to kill off units with just a smidge of health left. Don't be afraid to run away, the AI is terrible at running engagements--it often blows movement points unnecessarily even though it has a numerical advantage and would benefit by sacrificing an attacker or two (you can't afford that, ever).
You need to use terrain to your advantage for both city and unit locations. Long mountain ranges with limited gaps are a huge help, as are nearby city-states, as the AI won't generally roll attacking forces through city states. Of course, defensible city locations vs. productive city locations is a bit of a min-max problem. In an ideal world, you get a great starting position with a highly productive and defensible 2nd city location nearby. You can't play too cautious, you'll need to take some risks to try to get that second city running asap. My starting build varies a bit depending on location (and very much depending on neighbors), but it usually goes Scout/Slinger/X/Settler, where X is either another scout or another slinger (scout if you haven't found much nearby, slinger if there are barb camps everywhere). Your top priority is getting a slinger kill to get the archery bonus. I've never survived that initial war without archery (not counting island starts, which generally work poorly for deity, since it's hard to make up for their starting advantage with killing a few of their units or taking a city or two).
You don't want that initial war to last very long, rush strategies are very hard to execute on Deity and you need to get to building out and developing your empire. In the ideal war, it gets close, but strategic use of upgrades (particularly delaying them until deeply wounded) let you kill of all the attackers and then use multiple archers and your one warrior to take the city nearest you before it can build walls.
The next phase is trying to control as much territory as possible (note: NOT the same thing as building as many cities as possible). Again the AI's are going to way ahead of you in generating Settlers. You need to make sure that you block them from rich areas that will take time for you to get to. You're still behind on points throughout this (though if you're lucky in the initial war, maybe you're not last). The key is working ALL micro-advantages you can, especially city-state freebies through quests. Note that early city-state dominance IS achievable and sustainable against the AI, Deity doesn't make the AI any better at using city-states. Actually, the biggest problem are AIs that destroy city-states--causing you to miss out on a lot of potential bonuses.
You also want to maximize your benefits from exploring: goody huts can be really helpful particularly if they give you a unit or, even better, a relic that generates religion AND culture far beyond your limited ability in the early game. You should try to avoid researching unboosted tech or civics--you need those advantages to catch up.
A note on religion: you will have to prioritize it if you don't want all the religions to be used up before you can earn your first Great Prophet. It's not a death sentence if you don't form a religion, but you are missing out on some easy Era points and possibly cash if the AI wasn't smart enough to take Tithe.The middle phase is relentless microing and tradeoffs. Do you run an internal trade route to boost growth of your second city or use it to open a path through the hills and rainforest? Which district first? Keep building settlers when you don't even have city walls or fortified units? You should absolutely be trying to maxmize every district bonus, and take some risks. You won't catch up if you play it safe. One frustrating point is that even if you do everything right, it's likely you'll still be middle of the pack in technology. Civics seem to be a little easier to catch up to the AI, but they'll have an advantage in culture, since they can pump out more artistic Great People and Wonders while you're still fighting to build campuses and encampments.
Prioritize controlling luxuries. Until late mid-game, it's hard to grow without luxuries, so if you can sit on the majority of them, and stingily trade them 1 for 2 or even 3 (the AI gets desperate), you'll be able to grow your cities well beyond the AIs and start to win the productivity war. Also, when the AI is offers you a deal, see if you can force them to throw in luxuries as part of the deal. The AI will sometime make terrible deals because they want some random great work. Or open borders. Or an alliance.
Pick your safe allies and be super stingy with the top 1 or 2 by score. Avoid trading or allying with them (unless you're doing it to reduce the chance of war so you can cut defense spending).
You should be prioritizing Science while steadily building your productivity. If you do it right, your productivity advantage (because you have more people, more land, more natural and luxury resources) will start to win out over most of the AI players.
At the land runs out, you should expect yet another war from at least one of your neighbors. This time, try and take a major city of theirs, preferably with a wonder or two, but don't get sucked into a long war.
Even if you do EVERYTHING right, it will likely be a battle in the endgame no matter what victory you are trying for. If you are going Science victory, you should be picking your spaceflight super city very early based on which can produce the biggest bonuses for Industrial Zone and overall production. The production required for space projects is astronomical
so you need Governor help (Pingala--30% Space Project bonus) as well as Great Scientist help and policy cards that increase IZ bonuses. Also, reroute ALL your trade routes to deliver productivity to the space city (many people forget to do this, but it's critical at Deity).
Hope this helps. I probably played a hundred (or more?) deity games before I won, though I came agonizingly close a bunch of times. Lower levels can help you develop strategies, but Deity presents unique challenges because you simply cannot have it all, and you have to bend to the challenges of the terrain and opponents, rather than using the same cookie cutter strategies each time.
Good luck. It's worth it when you finally get it. You do also have to be a bit hardcore about quitting a game where bad luck has put you too far behind.
