It's going to be a while before we collectively have enough experience to answer this definitively, but based on my limited experience (and having read pretty much the whole PH on a long flight without anything else to do...), I think the answer is 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 going to be a lot more dangerous, and bad luck can really compound without any possibility of correction. A party without any recourse to combat healing will need to be a lot more careful — and, meta-game, the DM will need 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.
Adding 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. Also 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.