In the several years since 5E has been out, I've played at a lot of tables which often do not have a cleric — or any dedicated healer. From this, I think that you really want the healing role covered, but it doesn't have to be by a cleric or paladin.
Without healing magic, fights are a lot more dangerous, and bad luck can really compound without any possibility of correction. A party without any recourse to combat healing needs to be a lot more careful — and, meta-game, the DM needs to be a lot more careful to not kill the whole party with a middle-difficulty encounter.
As Joshua Aslan Smith notes in his answer, potions can help, but aren't really sufficient. But I disagree about other classes and abilities.
First, let's look at the healing power that the cleric class provides. A generic cleric actually gets nothing special here outside of spells — there aren't any healing features except for those from domains. And in fact, they are only from the Life domain. I'm going to go ahead and assume that the answer to this question isn't "every party not only needs a cleric, but they need a Life cleric"; that is, these extra features are indeed above-and-beyond.
So, that leaves the spells. And, obviously, clerics get a lot of good ones. The thing is, many powerful healing spells aren't cleric exclusives. A few options like 9th-level Mass Heal are reserved, or 2nd-level Prayer of Healing or 3rd-level Mass Healing Word, but the healing basics aren't:
- Cure Wounds: bard, cleric, druid, paladin, ranger
- Healing Word: bard, cleric, druid
- Lesser Restoration: bard, cleric, druid, paladin, ranger
- Greater Restoration: bard, cleric, druid
- Mass Cure Wounds: bard, cleric, druid
- Raise Dead: bard, cleric, paladin (and druids get reincarnate)
- Heal: cleric, druid
- Regenerate: bard, cleric, druid
- Resurrection: bard, cleric
- True resurrection: cleric, druid
Bard and druid get the same number of spell slots as cleric.
Paladins have fewer spell slots overall, none at first level, and no high-level spells. They do have the Lay on Hands class feature, which is nice, but I don't think makes up for it — if you don't have a cleric, a bard or druid with a healing bent is probably better at it than a paladin. A circle-of-the-land druid can even regain some spell slots during a short rest. And bards have the "Song of Rest" feature, making short rests more effective, plus they have an exclusive 9th-level Power Word Heal, plus the "Magical Secrets" feature allows them to actually learn those exclusive cleric spells after all — choose the College of Lore to start getting those at 6th bard level. In fact, I'd go so far as to say that a bard with a healing focus is likely to be a better "party medic" than a cleric who takes a non-healing path.
If you're using the Xanathar's Guide option, the case for non-cleric healers becomes even stronger. For druids, both the Circle of Dreams and the Circle of the Shepherd paths have significant added healing power.
Xanathar's also adds the 2nd-level Healing Spirit spell for Druids and Rangers; this is concentration-based spell lasting up to a minute which restores 1d6 hit points to every creature in a space. That's potentially 10d6 hit points to each creature who can move through the space, which is amazing for a 2nd-level spell. (And it adds more d6s if you cast it at higher levels.) Healing-focused druids using these options are also better party healers than non-Life clerics, and at arguably on par with Life clerics too.
And, also with Xanathar's, sorcerers and warlocks both get healer-role options in Divine Soul and Celestial patron respectively. Divine Soul opens up the cleric class list and adds a minor healing-focused ability at 6th level. The Celestial patron gives access to Cure Wounds and Lesser and Greater Restoration, along with a 1st-level healing power.
For any class, taking the Healer feat (for anyone in the party) adds a bit more healing, and that's never bad, but if you do have some sort of spellcaster focusing on healing already, I don't think it's necessary. But, if building a cleric-free party, take a look at the Acolyte background, which includes the "Shelter of the Faithful" feature — you can count on free care at temple or shrine of your faith. That's particularly good for getting rid of curses — or party deaths.
Overall, clerics shine when it comes to fighting undead, but aren't necessarily the strongest choice if you want a dedicated healer in the party. And, having such a "medic" party member really helps, although it's completely possible to go through a campaign and have a lot of fun without one.