I pretty much agree with evryone here - if you have time to get a religion, my usual technique is to use a disciple to get the 20 culture, which gives me enough time to get a monument; or I can use a second disciple for culture from the religion (harder with ROK). Or you can be creative. Or you can just fight.
Some of it depends on how quickly Loki gets out.
Perhaps just as big a problem as Loki stealing your cities, though, is Loki stealing the AI cities, and the Balseraphs become the runaway civ. Even on Emperor and Immirtal, I've run into trouble with the Balseraphs being just overwhelming; on deity, I usually find it just too tough.
Best wishes,
Breunor
Loki can be built on deity even before turn 20...
The thing is, you can try to get a religion early if you start with ancient chants. Granted, most civs start with that, but not everyone is philosophical.
I would not go mysticism>crafting>mining straight away without some wine or gold.
If I'm running a priest to get the religion I'm not using an Elders Council to use a scientist to help with research.
To go fishing immediately, I need not only a coast start but also some fishing resources to be worthwhile (well, if you are financial, it's not that bad even without fishing resources).
So, it depends on the leader and the land.
It definitely seems a situational solution.
(I definitely did not expect a general solution...)
I must say that on Emperor I never had much difficulty with them, and even on immortal if Loki comes my way I just declare war on them and give the middle finger to the AI.
I usually find that Loki's little games usually encourage the other civs to declare war on them more easily anyway. It is true that in some games they become overwhelming but I wouldn't say that that is typical and I'm more afraid of a big Bannor than them.
On diety, I don't like to get into a early war with them because they build freaks so fast. The freaks have, well, all of those freak promotions that makes them thougher than warriors.
With the Svartalfar, I'm still not disinclined in trying to get an animal in time. The thing is, you don't have to try to nail loki in someone else's city. That could also require cartography (there is no guarantee that you'll have Open borders with an AI that is more inclined to godking early on).
Loki casts a puppet pretty much every time he's not in a city. What happens is that he will typically cast a puppet before entering a city and only in the following turn he will disrupt it. Which means that you should have a specific turn to kill him in your city.
I say should, because I still have to try it.