I use a pally and like it so far. I like the buffs and blessing, and I have the option of playing her as ret or holy some day if I wanna split off of the group.

You don't need a dedicted healer for a paladin either, I use 4x elemental and just spam a couple lesser healing waves.

I think they are all pretty viable overall, I'd make whatever you prefer the most. Sometimes I wish I had a warrior or a DK. Warrior being my old main, I would respec and play her solo in a hearthbeat. Paladin on the other hand, I don't care too much for ret and I enjoy healing with a priest or resto shaman a lot more