One of the nice things about Paladins, is that (with high Wisdom) they can almost cover as primary healer, especially in a small party.
With say, 18 Str or Cha, and 18 Wis at 1st level (depending on race), your attacks will be potent and you will still have 4 uses of Lay On Hands per day. Granted you have to be in melee range with your fellows to heal them, but the ones in melee often need it most anyway.
There are a few Paladin powers that grant healing, so it's easy to improve your ability to keep the party up.
Multiclassing into Cleric, Runepriest, or even Bard or Warlord will be trivially easy and provide an extra Daily ranged healing power. Clerics have the best Power Swaps for healing, so if you plan to go that route, Cleric MC is probably the best choice.
A rather unconventional approach, but one that gives you the most consistently usable healing ability, is Shaman multiclass. The 13 Wisdom requirement is a given for you, and, if you invest a second feat (Mending Spirit), you suddenly have a ranged heal usable every encounter (the equivalent of taking a Hybrid Leader class), instead of once per day.
Whether or not this is worth two feats to your character really depends on how many encounters you think will be typical for your group in a given adventuring day. The other benefits of going this route include a Spirit Companion that can take space on the battle map, and once per encounter make an Opportunity Action, and the Daily use of Speak With Spirits, giving you a significant boost to a skill check.
As far as the fluff goes, perhaps the Spirit Companion is actually the departed spirit of a saint or angel from your religion who speaks to your character, giving advice, lore, and otherwise helping your character succeed against the enemies of your faith.