We don't need to have actual gods to have religious magic in a game. D&D and other fantasy games have a long history of making gods characters in the setting. Certainly there was plenty of inspiration for meddling gods from the stories of Greek and Norse myth. Some of the fantasy stories that inspired the original Dungeons and Dragons had extra-dimensional beings locked in a war between the forces of law and chaos that spilled over into the fantasy world. It was often expressed as a kind of dimensional cold war fought through proxies who were champions and spellcasters given extra powers by their extraplanar backers. It also mixed in the crusaders, saints and biblical stories. D&D, especially the older editions, calls back to the legends of the middle ages and invokes the Arthurian tales of chivalry and knighthood.
With such material informing the setting it's no surprise you end up with gods granting spells to clerics and special powers given to paladins. For me it's never quite sat right though. The idea of gods showing up, messing about with human affairs and having the odd affair of their own to create demigods has a certain quality to it, but it's more like the brat pack era of Hollywood than a group coming together over a common belief. Fantasy religions are less about faith and devotion to the idea than they are hierarchies with a supreme being at the top. They are more like corporations with clearly defined goals based on the godly portfolio coming down from head office.
With freelancers like adventuring player characters it's often a kind of contract. There's give and take with the godlike creature. Some characters who deal with extra-dimensional beings, performing sacrifices, other services and advancing their patron's goals in exchange for powers are called Warlocks/Witches/Cultists and others are called Paladins/Clerics even though at the core they are doing the same thing.
There's no reason why the existence of a god needs to be settled to account for religious magic. In a world where magic exists, reality is already disrupted. It can be bent and even broken with the correct pressure. In such a world a large enough group could form a kind of psychic pressure that could be used to disrupt reality in the form of miracles and other faith-based abilities.
A large enough group of people believing in an idea gives that idea power. The more people that believe, the more power that builds behind the idea. This power might manifest randomly in miracles and other unexplained phenomena. They could be mysterious like burning bushes, epic like earthquakes and thunder, or ridiculous like the visage of the god appearing in common food items like toast. Where it becomes interesting and gameable is when there are individuals who can tap into this power provided by the belief of faithful. People who can shape the will of others into particular effects like healing or even a plague.
These conduits of the faith would be as rare or common as is needed by the setting. They could be found leading a faith, drawing on the power of the faithful to perform miracles and gather more to their religion through these demonstrations of godly "intervention." They could even begin as charlatans who are suddenly surprised by their ability to perform real miracles thanks to the faith of their flock, despite having no belief of their own. The idea that a religious leader could fake it until they make it has all kinds of possibilities. They could also be individuals operating outside of a hierarchy as chosen champions, druids leading their communities, or even hermits serving in remote shrines.
It's the champions of the faith that are the most likely to become adventuring characters and played. Powerful missionaries carrying their message into the wide world or passionate believers living as examples in the dark times. Certainly a player character might want to build their own religion or religious faction of an established church. Depending on the campaign your group is into, the intrigue and challenge of creating a new religious order might provide the best adventure hooks.
When the characters get their power in the form of spells from some deity or demon prince there's not much incentive for them to do much in the way of religious boosting. If the character's power is tied to the faith of those following the same religion there is a good reason to spread the good word.
In game terms it could break down to numbers and distance. The larger the group the more power that would be available to an individual able to tap into it. How much of that power they could access would depend on the talent and experience of a particular character though. There would need to be some critical mass to get the minimum required to perform the most basic of miracles, the cantrip in D&D for example. It could be a number with some kind of meaning or completely arbitrary. Each level of power could require a different number of believers, growing exponentially from a single village to the population of a country or empire.
The distance would come into play as the champion moved away from the centre of religious belief. As they move farther away from the faithful the harder it is to tap into the psychic power provided by the belief of the masses. This could be overcome by setting up missions and chapels as outposts of the faith to form a kind of psychic corridor back to the power base of the faithful.
The idea that the smaller groups of worshippers could connect to the larger faith and carry the signal forward to the conduit of that faith like radio relay towers. If war or change disrupted the reach of the original religious organization the new churches could provide their own faith for the character to draw on. Regardless, there's an incentive for them to convert new followers and set up churches wherever they go. Also giving them something on which to spend any treasure they happen to find. The rest of the party might be keen to chip in since the one character's ability to access the power of faith affects their fortunes as well. The amount of available power would drop by one level for a particular distance so the faith of a theocracy might be felt and used on the far side of a continent or even ocean while a village of believers might only provide useful power out to a day's ride away.
As a factor of belief the faith magic becomes more dependant on religion and the religious instead of the terms of a contract with a god-like creature. This changes the game and creates some new incentives for players of religious characters to play their role as proponents of their religion or religious order. These are the reasons I chose this direction for the system and setting I'm working on for my own game but I don't see why the concept couldn't be used for any other fantasy RPG. It's just a matter of tweaking the setting a little.
In this model of using the common belief of the group as a source of magic rather than a god or group of gods gives the GM quite a bit of latitude in defining the place of gods in the game world. Their existence could be a question that is not answered, which is my favourite but certainly not the best. They could be remote and uncaring like Conan's Crom with the worship of lesser beings passing unnoticed. They might be like Terry Prachett's Small Gods that draw power from the devotion of mortals and are even created by it. They could need the worship to allow them power in the world. Perhaps with enough believers they could even enter it. That makes the Cthulhu cults a little more dangerous if they can frighten or bribe or fool enough people into devoting themselves to the great old one it might show up!
NOTE: This is an updated version of the original blog post. The original had an unnecessary definition of faith that people were stumbling over. I'd rather people engage the premise than debate my use of an overly simplistic definition, so I took it out.