I totally dig the pali + 4 ele sham thing for Heroics. I haven't had to respec one resto yet, but haven't cleared all heroics either (not cleared: MgT, Arc, CRypts, SL).

For PvP I just grabbed the healing set for the paladin and even without respeccing from a full Prot build I can do pretty well spamming flash heals on whichever shaman is the burndown target... I just setup actionbar 1 as my "tank" bar, and actionbar 2 as my "healer" bar for the paladin and that's worked out well with the gear swap.