Hey Psycho,
Been having a blast PVE mboxing for a few months now using HKN on Outland with a mixed team. Prot Paladin, 3 range dps, Resto Druid healer. I had some of your same issues earlier on, but it definitely smoothes out as you gear up a little. First did Ramps and Blood Furnace around lvl 64-65, was a little slow-going but made it through eventually. So I just decided to just focus on questing instead of wasting so much time on dungeons. After finishing most of the quests in SMV and NS, I took another bash at dungeons and steamrolled most of them in quest gear plus a few craftables. Have done most heroics too, some of which are a fun challenge but totally doable (including farming first boss of SHH 30 times for spellstrike hood pattern, on heroic, with no cc, because I like pain =P). Have geared my team up to around 2400-2475 GS through heroics and craftables/some boe epics, and now working on a second 5-man team to tackle Karazhan soon.
Anyway, all that to say that yes, prot pala is definitely successful for PVE tank. You'll be kinda squishy in dungeons until you gear up a bit at 70. But threat shouldn't be too problematic as long as you keep righteous fury up, blessing of salvation on dps, and make sure you got some +spell dmg gear. Use the Outfitter addon and make a high spell damage set to help with cutting through trash quicker and then switch to normal tank gear for harder bosses. If you're still feeling too squishy, drop a few thousand gold on some boe epics to jumpstart your gear - you should be swimming in gold from all the Outland quests.
Cheers!