Greetings!
Well, in a related thread, "The King's Rangers!(Reprised)" myself and Mmadsen venture at some length into a very similar discussion.

I encourage any to check it out.
With all classes in my campaign, I have granted an across the board bonus of +2 Skill Points, specifically to address this very problem. To wit:
Throughout history, there have been warrior-priests who, while being skilled in combat, were also quite the theologian and scholar. Read up on some of the priests from the 8th century AD-the 17th century AD. I've also read about a number of early American Puritans, who besides being military veterans, were fiery preachers, and brilliant theologians and scholars. They organized the establishment of towns, governments, as well as leading raids against Indians or other enemies. All the while, these men were often married, raising six-twelve children, and known for writing dense theological books and Biblical commentaries. They were often known to be skilled marksmen, able swordsmen, and ferocious with an axe or club.
The D&D Cleric does suffer pathetically. Even if a cleric is more martially bent, there is no good reason to believe that he shouldn't be good at Diplomacy; Have skill in Sensing Motive; and be expert on the history and theology of his faith. The whole "Game Balance" excuse is supposed to have been thrown out with the last edition. "Game Balance" was the often cried justification for every stupid restriction and dumb rule there was. It was becasue of such weak thinking that perhaps many people stopped playing D&D. Remember the "Wizards can't use anything more than a dagger! Why?--because of 'Game Balance.'" Your wizard is trapped in the tunnel, and the Troll is charging you. You're unarmed. The Wizard says, 'wait! Can't I pick up the dead fighter's sword?'" "Nope" the DM says. Why?--because of "game Balance."
It is with these thoughts that one should think carefully about the elements of realism and logic in approaching rules, or a character, as opposed to the slavish obedience to "Game Balance." I'm not saying game balance isn't important, and I hope I'm not sounding arrogant, but personally, because I like to be a logical person, consciously ignoring something that I know makes good sense because of some nebulous concept like "Game Balance" often just drives me nuts, you know?
I say give the Cleric more skill points, or if you prefer, provide the cleric class with a few bonus ranks in essential skills as part of the class background--say, +3 to each of the particular skills, like Diplomacy, Gather Information, Sense Motive, Knowledge-Religion, and Knowledge-History, for example. That way, even if the Cleric only seldom puts any points into those skills later on throughout his career, at least he will have a minimum proficient knowledge to function in society--not just in the damned dungeon!

--as a priest of the faith!
Semper Fidelis,
SHARK