Question 1 is "what's the deal with my cleric's religion?" There are a LOT of possibilities. Instead of going through them all, I created this set of tables to allow the quick creation of new religions for roleplaying games; it's not comprehensive, either in the possibilities for roleplaying or in covering all religions in real life. I should point out that using a real religion for your cleric is another possibility that is probably under-utilized and opens up all sorts of interesting possibilities we won't get into today.
A fun twist to put in your campaign setting would be having your players' clerics' religions be wrong about the the cosmology of the universe; if the clerics discover this, it could make for very, very interesting higher-level play as the clerics decide what to do with this information.
Who are the gods? Roll 1d8:
1: Atheist- there are no gods. There's still divine magic, but why is up to you.
2: Monotheist- there is one God, who usually created everything and runs the whole show.
3: Henotheist- there are many gods, but worshipers only worship one particular god; the default in vanilla D&D.
4: Polytheist- there are many gods and worshipers worship all or many of them. Clerics and priests would normally be dedicated to just one god, though that wouldn't stop them from worshiping other gods when expedient.
5: Ancestor Worship- the gods are dead ancestors and care about what goes on with their living families.
6: Animism- demi-gods or petty gods are everywhere. Every action and object has a demi-god that is in charge of it.
7: The Force- presumably self-explanatory. If your players aren't familiar with the Force, watch Star Wars instead of gaming for the next few sessions. Midichlorians optional.
8: Roll 1d4 times on this table and combine the results.
Who can join this religion? Roll 1d4:
1: Exclusive- this religion won't take converts; it's for the chosen few (race, class, being born into the religion, having a birthmark, etc.)
2: Esoteric- this religion will technically take converts, but they don't advertise and conversion requires a lot of work (and possibly gold). There may be secret knowledge learned only after levels are attained or at the feet of a guru.
3: Friendly- this religion doesn't place an emphasis on conversion, but converts are very welcome. Some individuals will proselytize with varying degrees of insistance.
4: Evangelistic- this religion actively seeks converts and all members are responsible to share their faith. Forced conversions may or may not be seen as legitimate.
How are the gods inclined? Roll 1d6:
1: Omnibenevolent- the god(s) of this religion are always loving and working for the good of their worshipers/the universe. Note that they may cause difficult circumstances "so they can grow."
2: Loving- the god(s) love their worshipers/the universe, but can be angered by betrayal, apostasy and evil, which they will punish.
3: Temperamental- the god(s) will generally be good to their worshipers as long as the worshipers fulfill every one of their obligations to the god(s); if they don't, bad things (spell denial, etc.) will happen.
4: Moody- even if worshipers do everything they are supposed to, the god(s) may not be in the mood to grant them favor today…
5: Apathetic- the god(s) don't really care what happens to mortals; the interest they take is strictly for entertainment. Note that they may meddle to make mortals' lives more entertaining.
6: Malevolent- the god(s) aren't very nice. Worship is generally to placate them and keep them from killing everybody. At its most extreme, we're talking Cthulhu and his ilk.
What is the moral code? Roll 1d6:
1: Amoral- this religion cares about transactional things like sacrifices and a good harvest, instead of any kind of moral code.
2: Laissez Faire- this religion teaches a moral code, but each person is only supposed to care about how well they as individuals follow the code.
3: Helpful- a moral code is seen as a helpful way to live the good life, so tenets of morality are regularly shared with those one cares about, but it's up to them to take the advice.
4: Societal- this religion cares about the health of society and teaches its moral code as a means of achieving or preserving a healthy society. Moral degeneration is seen as the precursor to the downfall of society.
5: Pushy- members of this religion try to force everyone, even non-believers, to adhere to their moral code because they fervently believe that that's the way it's supposed to be.
6: Roll again 1d4 times; there are different factions or streams of thought on morality in this religion.
How is worship done? Roll 1d6:
1: Sacrifice- the main act of worship is giving material possessions to the god(s), often by destroying them or donating them to a temple.
2: Service- the main act of worship is meeting the needs of either other worshipers or anyone in need; these can be physical, spiritual or both.
3: Praise- the main act of worship is corporate ceremonies where the qualities and/or actions of the god(s) are extolled.
4: Study- the main act of worship is to study the sacred texts and grow in understanding of the religion.
5: Mystic Communion- the main act of worship is individual communion with the god(s), usually while alone.
6: Ritual/Ceremony- the main act of worship is to perform defined tasks that please, placate, support or imitate the divine. (Thanks to Antion for contributing this.)
7: Public Devotion- the main act of worship is some public act; possibilities include telling a ruler off for abandoning the faith, acting out metaphors to get a point across to the apostate masses, self-flagellation or other public repentance activity, taking part in a regular parade for the divine (probably with some representation of the divine housed in a palanquin that they carry), etc. (Thanks to Antion for indirectly suggesting this.)
8: Roll again 1d4 times. This religion has more than one major act of worship.
What level of religious involvement is required of those who follow this religion? Roll 1d4:
1: Assent- this religion doesn't get involved in life much; members just kind of know there are gods that they occasionally worship.
2: Regular- worshipers regularly go to sacred places to perform worship, but other than that the religion doesn't affect their lives that much.
3: Worldview- the worshipers view of life is fundamentally shaped by their religion and it affects many of their choices, but they can easily be confused for someone who doesn't share their religion.
4: Lifestyle- this religion affects all areas of life and worshipers always wear articles of clothing or jewelry and perform rituals or prayers that make it obvious to all that they are members of this religion.
What spheres of influence does this god rule over? Roll 1d4:
1: All- this god reigns over all parts of the universe.
2: Many- this god is responsible for many aspects of life or areas of control.
3: One- this god has one sphere of influence.
4: None- this god has power, but isn't associated with any one part of life or realm in particular.
As an example, I just rolled up a religion that is monotheistic and has an apathetic god that doesn't exercise control over anything in particular, but whose worshipers are an exclusive group that pushes their morality on everyone, practices service to others as their primary mode of worship and wears religious clothing and perform rituals and prayers throughout each day. It sounds like one way that believers in Crom might react to his apathy: "if Crom won't help us, we'll help ourselves and each other." They probably got their stereotypical paladin attitude from the fact that others not buying into their religion and moral code could destroy an entire village in the unforgiving environment where this religion was founded. Their moral code probably revolves around helping others and keeping the impact of one's actions on others in mind when making decisions; their dress is probably mountain dress, even if they've migrated to another, more hospitable place (moving to an unfamiliar place filled with people you don't understand can be an impetus for intolerant, emotional and judgmental religious fervor). Their rituals might include asking everyone they meet if they need a place to stay for the night or if they need a meal or other need. You get the idea.