Made a rookie mistake of letting my players (who have never played DnD) choose what class to play without discussing with me or each other, and we ended up with no healer. We've already played quite a few sessions, which have been very combat-light and more story-based, but I want to challenge them a bit now that they're about level 4. However, I would like them to not die. How can I make battle encounters balanced with no healer, besides just giving them a bunch of healing potions?
You need do nothing.
Having a healer is nice, but it's far less necessary in 5e than it used to be. It's actually pretty difficult for characters to die in this version. A few potions will be a good idea. A few Healing Kits for stabilizing anyone who goes to zero. Maybe someone takes the Healer feat. Maybe someone takes the Magic Initiate feat, and goes with cleric. Or even someone dips a level in Life Cleric.
Few battles last long enough for people to die in, even if they get dropped to zero hp. So if the party is vigilant to keep an eye on anyone that goes down and to stabilize them before they fail the 3 death saves, they can then take rests as needed to heal back up. According to the rules, a short rest can get you back most of your hp and a few of your resources, and a long rest all of your hp, spells, etc.
So, to directly answer your actual question: I would do nothing to "make the battle encounters balanced with no healer"; it isn't necessary.
Come to think of it, I don't think I've played with a 5e campaign yet that had a serious or dedicated healer.
In the campaigns I've played much in, one went through Out of the Abyss with a 3-PC party of a fighter/rogue/warlock multiclass, a battlemaster fighter, and a vengeance paladin. The other campaign had a large party in a homebrew world, and little healing: champion fighter, eldritch knight fighter, druid, assassin rogue, shadow monk, wild magic sorcerer, beastmaster ranger, wizard.
The campaigns I've run for, one is a smaller party, of a barbarian, battlemaster fighter, wild magic sorcerer, vengeance paladin, and sometimes an NPC valor bard. The other is again a large party, but little healing: champion fighter, thief rogue, vengeance paladin, valor bard, moon druid, warlock, barbarian, fighter/knowledge cleric multiclass.
It looks so far to me like 5e can work pretty well with almost any combination of classes and races, so I'm inclined to not worry about that, and let the players play whatever they want to.
There are several ways forward with this situation.
An NPC (or "DM-PC"). You can introduce an NPC into the party, to fill this role. Not only does this introduce that extra buffer against death, but also shows the party the value of healing abilities.
This was the solution to one of our games, That had 2 Barbarians, a Fighter and a Rogue. The DM introduced a Druid NPC, And while we had never quite reached the brink of death, we had always come out the other side a lot more worse for wear. The Druid NPC certainly helped keep us on our feet with the ability to cast Cure Wounds on whomever was in the most dire situation.
Multi-Classing. If your party feels they need the healer, perhaps introduce them into multi-classing. It might be a bit of an advanced tactic, however, especially for beginners.
More rests. Not only is resting is how the party heals, but it is also how they recuperate their abilities, and especially for the spellcasters, having a few extra spell slots under their belt can prove helpful in a tight spot.
"Injured" Monsters. It's possible to weaken a more impressive monster, for a bit of a different reaction. A Higher level monster, with perhaps a weaker AC and lower HP pool can give a different sort of combat - a higher challenge, but with only some of the risk.
In my experience, this certainly does raise the bar. I once had a run in with a Troll (CR 5), when the party was only level 3. We were definitely freaking out, especially when the warlock decided they wanted none of it, and bailed. Fortunately for us, the Troll had a broken arm, meaning it had trouble hitting us, but when it did hit... it hurt a lot. On top of that, it only took us a few rounds of coordinated combat to get some decent hits in, to finally kill it, since it appeared to have already been in a previous battle, and therefore only had a partial Health Pool.
Fudge your rolls. This is a slightly risky tactic, because if you do it too often, or at the wrong time, the rest of the party might pick up on it, and it can ruin the effect that you are trying to achieve. Being the DM - the one running the game and making it fun for everyone, this is something you can do.
All that being said though, the whole point of the game is to make it fun for everyone. Talk to your group and find out what it is about the game they enjoy, if they find the game challenging, and if that is a good thing, and discuss whether or not to raise/lower the bar. It might even lead to less combat, more puzzle solving or dungeon delving, dealing with traps, etc. Or even just more RP.
I had a party consisting of a Monk, Fighter and Sorceror (no Rogue) and I've noticed that it doesn't matter all that much. I pushed them pretty hard (plenty of Hard and even some Deadly encounters) and it took them 3 sessions before the Monk died, and that was only because they got sloppy and decided killing the last retreating enemy was more important than stabilizing the Monk, who then rolled a 1 and died.
So really, I'd suggest just seeing how much they can handle. Throw them some Hard encounters that have an easy "out" (a way to retreat, surrender, or end with them captured instead of killed if they lose) and watch what happens. You might be surprised by what they can do. I sure was.
The 5th edition rules are pretty generous about out-of-combat healing, so I assume your concern is with party members falling in-combat. There are three paths I can see.
First is to provide them with in-combat healing. That could be "just a bunch of healing potions" after all, or a hireling/escort. Providing them with a (finite) stock of healing potions might not be the worst thing in the world, since it forces them to consider action economy and supplies. But you did ask for alternatives.
I ran a DM character, a non-theist cleric of Healing and Chaos, to fill this role in an earlier edition of D&D (3.5). (The character was deliberately made unreliable so the players wouldn't treat it as a free hireling.) While I don't have experience doing this in 5th, it seems to translate well to the mechanics of the setting. In particular, the ability of players to easily craft healing potions in 5th seems to deliberately support consumables-as-healing.
Second, and my preferred option, is to design encounters in a way that allows them to run away and regroup. You could work some lessons into the world about people too stupid to see themselves in over their heads to foreshadow that this might be a possibility. Good encounters for this are encounters in forests or cities, where there is an abundance of cover; or encounters with the stated aim of delaying/hampering/leading away an enemy the characters can out-maneuver but can't hope to beat (like an army, or a blinded rampaging troll). One long rest later, any of that damage will vanish, and they can plan their next move.
I call this my preferred solution because it's my typical way of handling both under- and over- confident groups, particularly small groups that can't bring every role. In a single-adventure (three session) game with a rogue, paladin, and sorcerer, the players incorrectly believed that the paladin would be able to supply all necessary healing. Instead of the TPK they were facing after a head-on combat against superior numbers went poorly, I allowed them to "re-do" the fight; they took a guerilla strategy with the sorcerer using Fog Cloud (in a 3rd level slot, obscuring the entire field of conflict) to cover a retreat. By breaking the fight into manageable chunks, they were ultimately able to triumph.
Third is to kill a character and encourage the player to re-roll into a healer. I've never tried this, but your question doesn't rule it out.
Use the DMG's table designed for this purpose
In the Dungeon Master's Guide, on page 82, there is a table called XP Thresholds By Character Level. This table, along with the other information in the encounter building section, gives you a good idea of whether or not you can expect a character to die.
Hard is described as
"[...] Weaker characters might get taken out of the fight, and there's slim chance that one or more characters might die."
Deadly is described as
"A deadly encounter could be lethal for one or more player characters. [...]"
So it sounds like you're looking for a Medium to Hard encounter.
Of particular note is nowhere in this section does it describe party makeup.
I have DM'd or played in 5e for a number of parties of varying class compositions, sizes, and levels. Most of those were at or below level 12. I've found the table to be pretty accurate, regardless of any of those factors. In particular, I've never noticed healing (in excess or lack) to have an impact on which category the encounter fit into based on their descriptions. There are two confounding things I've seen. First is when one side is resistant to most or all of the attacks from the other side. For example, a primarily physical group (level 2 fighter, ranger, rogue, paladin, wizard) had trouble with a physically resistant Will-O'-Wisp. Second is at first level. Characters tend to have so few hit points that a lucky critical hit from a goblin can down a max HP character instantly.
There are two mitigating factors to explain this. The first is preemptive healing : killing a monster is like healing all the damage it would have otherwise done before it died (or otherwise left the fight). The non-healing classes make up for it by being better at combat, so you can expect somewhat shorter combats than you would with a healer1. The second is the gratuitous amount of healing a character gets from short and long rests.
And yes, if you feel you need to, you can supply a few healing potions just in case.
1 Non-boss combats in my experience are usually about 3-6 rounds. More damage will put you on the lower end of that.
Healers aren't really all that necessary in 5e, and are somewhat useless until around level 5 anyway since until they start getting extra abilities their standard healing spells only heal about the same amount as a character can expect to take from a single hit in a typical encounter. So, action economy wise, a healer doesn't really increase the odds of surviving a fight much more than just another combat character. A healer at low levels can get a party back on its feet quickly if they're forced to go from one encounter right to the next, but good planning should be able to avoid the necessity of doing that. A couple of healing potions for emergencies and a healer's kit to make sure people don't die too easily will cover most of it, and jar of restorative ointment will handle poisons and disease, although it's listed as "uncommon" so they'll at least have to go to an actual city to find one, and it won't be cheap. The first 5e campaign I played in we started out with no characters capable of magical healing, and the only effect was that having a good strategy for rescuing downed characters and providing cover to the one doing the rescuing became highly important during the tough fights, along with having a plan for how to retreat and where to hide while the wounded recovered.
If lack of a healer turns out to be a problem for some part of the campaign, the simple solution is to give them an opportunity to hire an NPC healer. Being able to hire help to solve particular problems lets you throw a wider variety of challenges at them. Can't solve the puzzle in the ancient temple? Hire a scholar to help figure it all out. Don't really want to kill the pack of dire wolves that have moved into the catacombs? Go talk to the local druid and see if you can persuade him to help. Can't carry the massive pile of gold the now-deceased dragon was sitting on? Low-level porters are relatively cheap.
5e hireling rules are pretty sparse beyond a skilled person wanting at least 2gp/day, and the statement that people with more than basic proficiencies will definitely want more. So you'll have to put some thought into how much a cleric would charge to join the party. (Probably a guaranteed minimum per day plus either a cut of the loot or some kind of hazard pay on the days that have fighting.) On the other hand, this adds roleplaying opportunities and forces the players to plan ahead a bit more about just what resources they're likely to need to take on a particular section of the plot. If you need some inspiration about what's likely to cost what, the AD&D hireling rules are probably a good starting point.
You can, in fact, integrate hirelings even more with the setting. A level one party heading into a kobold lair all by themselves is somewhat ridiculous from my point of view. They generally have to find a lair with a tiny population that's inhabited by especially lazy and stupid kobolds in order to survive. A nest of "Tucker's Kobolds" can easily wipe out a standard, mid-level, 5-character party just by being smart and devious. Really the whole idea that a typical adventuring party is going to be four or five people (even when taking on major, world-ending quests) works only because there is a higher power ensuring that the party meets challenges appropriate to their abilities and that the monsters aren't that smart. Remember: Robin Hood had, at a minimum, 20 men; and some versions of the stories say he had closer to 140. The 5e game engine gets rather slow when you start throwing around that many pieces all in one combat, but that's what the UA mass combat rules are for.
So instead of starting out as a tiny, squishy party doomed to die horribly but for the grace of the DM, have them hire on as porters or support crew for a higher-level party. Then you can have the monstrous settlements maintain a fairly consistent level of challenge, and what changes is the PCs' position in the hierarchy. In the beginning their only responsibility is to guard the horses, and by the end they're in charge of gathering intelligence and planning the entire expedition such that they'll have sufficient resources to survive and make a reasonable profit and be able to carry it all home.
Of course, this rather assumes that the group you have would enjoy strategic-level plotting. If they just want you to lead them through a story arc with a few tactical combats here and there, then stick with letting them find potions for sale or as loot to cover the few spots where they'll actually need healing spells. The extra damage output from having another combat character instead of a cleric ends up making the party just as combat capable in most situations. Possibly moreso if they get split up somehow.
Go with Medium to Hard encounters (as suggested in another answer) until you have a better sense of how they will fair. After seeing the performance in these encounters, re-evaluate if they are struggling. As a PC in a campaign with three non healers, and as DM of a different campaign with three non healers - it's not terribly difficult to navigate combat encounters with no healer in 5e. As pointed out in another answer, higher damage output leads to sooner enemy death and dead enemies do zero damage.
As you don't want to just give them a bunch of healing potions, how about sending a healer NPC with them?
If your idea of challenging them combat-wise includes some quest giver, that person might send a healer with you, either explicitly as a healer ("You don't appear to have a member proficient in the arts of healing. My good friend xxx is, and he could accompany you.") or implicitly ("My friend xxx will show you the way. Good thing he also knows a bit about healing.").
Or he might require them to hire a healer somewhere ("Ah, I think you'll find a lot of resistance there. You'll need someone to patch you up. Come back when you've found someone to help you.")
Seeing that NPC healing them (but probably costing quite a part of their gain) might inspire one of your PCs to go multiclass and take up a secondary career as a healer.
@doppelgreener asked whether these options are from experience or from "armchair speculation". Thus...
As a player I have experienced a number of times NPCs being sent along with us providing relevant help of one kind or another. Usually that NPC either was a guide though unknown or difficult terrain or a person to support or protect on his way.
Once or twice the help was that of a healer in a group without any healing abilities; the NPC then was a guide who - happily enough - also could provide some healing. And indeed, we eventually started provisioning for healing ourselves.
The option of the quest giver requiring the group to bring a healer along is, admittedly, an extrapolation from there without in-game experience, and the DM should take care with that: One never knows where the players will go looking for a healer...
You can play to the party's strengths and make encounters that encourage faster damage. Have an enemy that spawns minions that attack them individually, someone who gets stronger each turn, an aoe attacker, or having to get through enemies to deactivate a device in time, someone who heals every turn. The possibilities are endless.
They might not be a maximally efficient/versatile general adventuring party, but instead you might find them able to specialize in certain types of enemies