Everyone's giving you bad advice. I would suggest they try to actually multibox this group composition before shooing other people away from it. Or at least give reasoning to your logic. The forums are here to share information, not to be snotty little brats because someone doesn't use the "perfect spec" or the "perfect leveling route". It's a game, people like to have fun with it, now play nice boys.

Prot pally + shaman works fine, aoe is fine -- the problem with magma totems/fire nova totems is keeping the aggro off the totems (since they have 5hp and are easily 1-shot by critters). Have the pally consecrate and you can aoe away. (Psh. Shaman have no aoe. Yeah. Right.)

Check my sig for 4x shaman 1x prot pally videos (pre-RFD I used a warrior and swapped the pally in and out since I already had a prot pally leveled to 40 prior to multi-boxing)

As for the ability of a 4x shaman 1x prot pally to perform in comparison to a more "standard" group, let's compare Suvega's 1x war, 3x mage, 1x priest group with mine. I was able to clear Ramps at 61 (dinged 62 upon downing the last boss) while Suvega struggled with 3 mages, a 65 warrior, and a 70 tier 5 priest.

It is perfectly viable -- shamans mitigate more damage with mail so are more forgiving when pulling aggro, grounding totem is awesome spelldmg mitigation for the pally, earth shock is awesome, stoneclaw can act as a temporary CC (like the adds on Omor), ranged taunt works WONDERS, pally aoe aggro is amazing, and with almost 5 "dps"ers things go down like rocks. Chain lightning is better than aoe, imo, since it's ranged and allows time to range taunt if there's accidental aggro pulls. Everyone can rez, there's wipe protection 5x an hour counting DI.

On a side note, from 1-60 questing is WAY faster. In outlands, that would depend on how much world pvp is going on. Typically instancing alone is slower than questing... if you can go through all the quests without getting camped.