It does matter in what period of history you are writing in though.
Yes, of course. I keep in mind medieval societies like France, Italy, Spain and so on in 11-15th centuries. Crusades, heretics burned alive, total wars, and so on. Later on (since the Renaissance), we can see gradual development of elements of civil society till the moment they took over and completely destroyed the old system.
Stalin got rid of god and demanded that his people did the same (although he would use religion when it was useful for him)
Well, Stalin didn't exactly get rid of God. He along with other Bolsheviks got rid of the old Orthodox Church that tried to resist their attempts to control everything and everyone. Stalin restored the Church (under his full control, of course) in 1940s during the WWII. In addition, he implemented a new system of beliefs very similar to religion (building bright future for next generations, freeing the world from nasty capitalists, we fight and die to let out grandchildren live happy, everything like that). And he took the place of God in this system. That's why the very people he exterminated shouted his name when his executioners shot them and beat them to death. That's why he's so popular today - religions rarely die completely.
Many dictators since then used the same method. However, such a system rarely works against the dictator's closest supporters. They know him too well to fall victims to such tales...
So maybe in my world, instead of some political coup or ruling with absolute fear and terror my dictator could have complete rule because of religion.....
It's a good idea but then your should explain very carefully why your society is so prone to religious tales. The higher the technological level of the society is, the more educated its members are, the lesser people are inclined to behave on the basis of purely mystical matters.
Kings/Emperors/etc have frequently used religion to justify their rule, but this wasn't always the primary source of their power, and losing the backing of the faith was not necessarily lethal to a king's rule.
Of course, they always had the army and their vassals to lend them support.
A weak king inevitable became a puppet of lords or was killed by another candidate to the throne. However, religion was always among the most powerful tools for controlling the society.
In Chinese history, Confucian beliefs teach that when the ruler is virtuous the land is healthy/prosperous/peaceful. Therefore if the land was impoverished and violent, the ruler must not be virtuous, so it was okay to overthrow him.
One small addition: the ruler of the land was always an appointed state official, not the emperor.
If something went wrong, that official would have been recalled and replaced by another one. However, no one ever disputed the power of the emperor, the Son of God. Even rebels and bandits respected him (or sometimes her). It's completely another matter, of course, that the emperor was often a puppet of his courtiers.