In my games, typically, the gods don't grant Cleric spells... Clerics just think they do. Like any Sorceror, Wizard, or Psion, the Cleric's spells come from his own inner strength, and his skill in manipulating the magical energies around him (proportions of each depending on which caster you are). While Wizard spells are shaped by formula and study, Sorceror spells are shaped by heritage and will, Cleric spells are shaped by their belief. The reason a Cleric's domains are limited by their deity is that their faith is based on the ideals of that deity-- which is why godless/philosophical Clerics also have limited domain selections.
I use Evangelists in my games as well, but they are shaped more strongly by personal experiences with the faith, and less by dogma, which is why they are spontaneous casters and why they have a slightly wider selection of domains. They're almost making up their religion as they go along.