Regarding Deity level, I've always thought the AI's must have greatly reduced maintenance costs alongside numerous free promotions and cheaper build costs as early on I often face attacks by 20-30 veteran warriors from civs that have only 3-4 cities of size 6 or less. One time, I discovered on turn 6-7 that a stack of 6-7 combat units was moving towards my city. How did they know I was there and how did they build and maintain 'em?
Regarding the Elohim: I doubt they get free maintenance costs at Deity level. I'm surprised and pleased to hear they're doing well in your game as in most of my Deity games, the Elohim do very poorly - usually they get knocked out in the mid-game after establishing a mediocre state. Seriously, they're rarely a contender for anything except Miss Congeniality. One of the weaker civs for the AI I'd say (and a thread about which civs the AI plays well, suggested many people rarely saw a powerful AI Elohim civ) and if they're getting free maintenance, they're not making the most of it.