City God. In ancient times, it wasn't unusual for a city to have a patron god. The god may be of something the city is known for, like commerce or agriculture, or there may be one "big" god in the pantheon with a different name in each city. As the fortunes of the city rose, the worship of the god spread. You might decide that your character strongly associates with his town and its deity. Perhaps he's not particularly religious but sees the faith as a means to power. This is a setting issue, so talk it over with the game master.
Local Temple. The idea that someone would chose their religion is a mostly modern invention (except for Dilettante below). In places like medieval Tibet, the local temple was essentially the feudal lord of the region. Those who were destined for a religious life practiced the local religion. Rivalry was not uncommon. Likewise, most people nowadays practice the religion of their family. This could be a wonderful background tie in for the cleric whose a seventh generation priest of the sun god. Likewise, a doubting Thomas can be fun; someone who isn't sure the religious life is right for them. Give them a secret vice. Perhaps plan a crisis of faith and work towards it, ending with a character class change or a re-invigoration of their faith.
Fallen Religion. Sometimes religions are expelled or discredited, often because their priests get too involved in politics. A disgraced cleric is an excellent role-playing opportunity. Perhaps his god died in a cosmic war, but he refuses to give up, choosing to worship general aspects of the god as his domains to gain power, but still venerating his god in name. Perhaps he worships a religion of a deposed empire, tolerated by the new rulers only because the populace would revolt otherwise. It's important to be somewhat obstinate about maintaining faith to provide the most role-playing opportunities.
Dilettante. The exception to local worship are those with power or money to travel and sample other faiths. Many modern religious sects borrowed extensively from other religions. A character might be a devout follower of a foreign religion or if motivated, may wish to include foreign ideas into an existing faith. Imagine a rich noble cleric who visits a far off country to study the ways of their sun god with hopes of returning to include those practices (possibly more powerful) in his home pantheons sun god worship. He may be looked on as a savior who can re-invigorate the faith, a heretic with incorrect views, or a pure opportunist, intent on raw power. Plan on how the character can plot their ascendancy across the levels. Attempt to rise in church power, create an inclusive new sect, or split the faith. The alignment of the religion will likely determine the outcome.
Pantheistic. One decision to make is how dedicated a character is to one god versus the entire pantheon. The Eberron setting, for example, frowns on a monotheistic dedication to a single god, unusual for Dungeons & Dragons (monolatrism is the correct term, since it's acknowledged that the other gods still exist). You can make an interesting character by mixing this up. Try a devout character who deviantly worships the entire pantheon or a "heretic" who chooses one god over all others. A character might choose to focus on a domain or two, like good and justice, taking inspiration from gods that exemplify these characteristics. Perhaps there's a practical reason why worshiping a single god or the pantheon is forbidden. I once played an Eberron character who worshiped a sun god of a slightly different alignment. He experienced such painful burning from the gods light during prayer that it led him to some extreme behavior.
Monotheism. Not venerating one god over others (monolatrism), but believing that there is one true god, whoever that is, would be an extremely controversial position. When faith is manifest in observable power, it takes quite a piece of work to deny the obvious. Go for it.
Philosophical Positions. Planescape provided a variety of philosophical positions about religion, readily integrated into a character background. Athar believe that gods are just really powerful beings and not worthy of worship. Godsmen took a normally heretical view that your goal should be to attain godhood rather than worship a god. Bleakers denied the existence or relevance of any religion, an astonishingly controversial position in a medieval world. These are excellent philosophies for non-religious characters, but imagine including one with a religious character!
Urban Choices. I like to give my cities tons of gods, Lankhmar style, with more gods than can be counted. At such a cultural cross roads, there will be some gods or even pantheons that rise to prominence, usually for political reasons, but veneration of other gods may be opportunities for someone without strong political connections or money. Perhaps the destitute character of the discriminated race finds a means to power and purpose through an obscure foreign religion.
Good vs. Evil. As much as possible try to stretch the reasoning for why a character would worship a non-normative god. What in his background drove him to worship the god of the dead? Was he so appalled by undead that he wished his ancestors to rest peacefully? Does he worship the god of pestilence and disease because he lost his family to illness when he was young? Don't just envision a well intentioned good cleric worshiping a "bad" god, what kind of deep character flaws can you give your cleric who worships a good god? Like anything in the game, it's often fun to come up with extreme examples. Heroes are already extreme, try to stretch it a little further.
Baal, or whatever they call him in your town
