I levelled to 80 with Paladin + 4 x Elemenal Shamans.
Once I first tried Heroics, I found that having a dedicated healer made things much easier. I really like earth shield. Now that my gear is a bit better, on heroic instances that I farm (not that many yet), I even DPS with the healer too to makes things quicker. It makes her a bit thirsty, but that not too bad.

Globally, I think hat having a dedicated healer makes my run much easier in the sense that it is less stressful, and I don't wipe as much on stupid mistakes ("I have time for another round of lightning Bolts before I start healing ... OOps, I didn't, tank dead ..." kind of thing).

You should probably try both ways and see what works best for you.