Right now prot pally is some OP shit... you get your avenger's shield right off the bat, a boat load of hp and mitigation, and some shiny bubbles to keep you rolling. Also, a free, insta-cast heal (Word of Glory) that uses the new Holy Power resource, which is garnered through using your Judgement and Crusader Strike.
At higher levels, I know that I've been having issues with Shadow Priests as well. They get to bubble themselves, drop fear bombs, absorb dots for more mana (I think), mind flay you to keep you from getting to them, and just in general melt your face.
Shamans are pretty badass too, with their quick cast heals, totems, decent armor, and versatility in combat style.
I know you said no rogues or hunters, but consider the subtlety rogue who shadowstep-ambush's you for 2k, then pops off an eviscerate for another 1k. Ouch. And the hunter who traps you, jumps away, slows you down, and peppers you down while you try in vain to get to him, or are distracted by his annoying spider webbing you in place.
Frost mages are good too, a perma pet, lots of snares, some shiny insta-casts, another class with a bubble, and the infamous polymorph. It heals you while you can't control your actions, but leaves him with plenty of time to steal the flag in WSG or cap the node in AB.
Druids are fun and all from a gameplay standpoint, but really, they try to do so much at once, that they end up underperforming at everything, except as maybe a flag carrier.
Warriors and warlocks, while each hitting hard in it's own right, don't really have any survival skills. If you decide on warrior, definitely go prot so you can charge in any stance, and at later levels (not sure exactly when) while even in combat. Warlocks, I'm not too fresh on. They have the capability of stunning you in place with Hand of Gul'dan, and then nuking you down while you're stuck there, but if you can get up on him or get him silenced, he's as good as dead.
Overall, my opinion would be to go with the Flavor of the Month, and roll a prot pally.
