This is not marathon but the same principle holds. Get out an ancient UU and conquer the world. Immortals, vultures or praets take your pick...
This is also not Epic speed. This is Normal speed and most unique units become obsolete rather quickly. Of the earlier unique units, Praetorians will obsolete the slowest. Using them is your best chance for an early victory. Immortals or Vultures will probably become obsolete before the 2nd Civ is eliminated.
Slowing down the Research rate of all Civs may be one way to give early unique units (other than Praetorians) the extra longevity they need to carry you all the way to Domination Victory.
I expect that decreasing the Land Domination Threshold by increasing the Number of Opponents may be counter-productive. I expect that beating 7 Civs into submission and spamming fewer Settlers to achieve a somewhat lower Land Domination will be more difficult than beating 4 Civs into submission and spamming more Settlers to achieve a somewhat higher Land Domination.
Building Warriors to steal Workers most often doesn't work very well on Deity level. When it does, the Civ will stay Mad at you until an Event allows you to speak to each other and gives you the option of Peace. At Normal speed, it will almost always be faster to build a Worker than to steal one.
I've only played one Normal speed Deity Domination game to completion. It was the proof of concept for this Gauntlet. It can be found here:
http://hof.civfanatics.net/civ4/game_info.php?entryID=15875
I have no doubt that it winning date of 300 BC will be smashed by this Gauntlet, but that's OK, since it is a Tiny rather than Small Map.
I suspect that 4 Civs on a Small Map will not be much more difficult.
To keep the Land to be Dominated as small as possible without increasing the Number of Opponents, I'd suggest a single continent Map (including Terra) with a High Sea Level to reduce the Land Tile count as much as possible. This should reduce the number of military units and Settlers needed for Domination to the smallest Hammer cost needed to build them. I plan to suggest specific Map types later with reasons for the choices.
Picking Opponents is a must. Probably the best Opponents to pick are those that produce the fewest units like Gandhi at 15%. Opponents that are late to research Bronze Working are another good choice. Opponents with High Peace Weight seem good, since they are less likely to back-stab. It may be best to stay away from Creative leaders whose Cities increase their Cultural Boundaries very quickly at Normal speed. Aggressive Leaders are bad for obvious reasons. Protective Leaders are even worst. Civs that start with Mining are usually bad, since they are that much closer to Bronze Working. Also, stay away from Mansa Musa (Skirmisher), Hammurabi (Bowman) and Rome (Praetorian). If your primary military unit is Axeman or Axeman based, also stay away from Civs with Immortals or War Chariots when playing Warlords or BtS. My Opponents will probably be Elizabeth, Gandhi, Lincoln and Roosevelt (same as in my proof of concept game). If you plan to use mounted units, avoid Civs with unique units based on Spearman like Greece, Maya and Zulu.
Well, that all I've got for now on winning as early as possible.
Sun Tzu Wu
)
. Liz had redcoats but never declared on anybody. Prats n cats vs castles isn't fun 
.
