Unlike most everyone else here, I don't see a problem here at all. You warned people that magic use has consequences:
Most (80%) of my players start off as a magic user, sorcerer, warlock, wizard, ranger, bard, arcane trickster, eldritch knight, etc. despite this premise. I allowed (so many of) them, but reminded them there might (or will) be consequence later for magic users.
They chose to ignore it. Maybe this is what they want to happen. Frankly, if my DM warned me during character creation that, "At some point, there will be consequences for magic use," I would not at all be surprised if, suddenly, there were dire consequences for magic use! You told the PCs that magic wasn't going to be reliable like it is in most campaigns. I'm struggling to think of what else the party might think you meant.
Let the story play out as presented, particularly if the PCs are going to be responsible for resolving the problem with magic in the world. I would change little to nothing, although I might drastically step up the foreshadowing.
About the biggest change I might consider would be to allow cantrips to be used with minimal or no difficulties from full spellcasters (and only full casters). In that instance, a spellcaster still has not insignificant combat abilities.
Furthermore, all your PCs can multiclass. Especially if you time it right, you can set it up so that the PCs will be 80% of the way through level 4. When they hit level 5, they'll know they need to pick up some armor and weapon proficiencies. I find it unlikely that none of them could multiclass to fighter or rogue; very few players will dump Dex as a spellcaster.
I'd also recommend allowing your PCs to select feats. Feats are a good non-magical way to increase combat power. You may also wish to use the Alternate Rewards section from the DMG to grant non-magic item rewards to your players.
Finally, if it's really not working, you can always change to a different campaign. "The PCs fail because the players made poor decisions," is a perfectly valid way for a campaign to end.
As to the actual question for encounter balance:
In spite of what many people think, encounter balance is extremely flexible in D&D 5e. IMX, combats go bad due to bad die rolls more than anything. In order for the Short Rest mechanic to work, the game's designers set the standard encounter difficulty low so that each adventuring day could accommodate the 6-8 encounters that are required to have multiple Short Rests. If your full spellcasters have access to cantrips (i.e., they still have something to do in combat roughly on par with a weapon attack), I do not believe that you'll need to change anything at all until you get to very high level (level 13 or higher). At worst, all you've done is make the Standard difficulty into Hard or Deadly. That's not bad; it just means that your PCs will have to be more discriminating about combat and more reliant on hit dice and long rests for healing.
The only other thing I see happening is that, at higher level, many obstacles require magic to overcome. Planar travel, magical diseases or curses, magical flight, flesh to stone, raise dead, freedom of movement, greater restoration, etc. All those become unavailable, so you'll have to be careful about the types of attacks your players suffer. You'll just have to be conservative at first, as well as generally flexible and willing to play it by ear.
At the end of the day, however, the published challenge ratings aren't going to be much help. Your PCs will still be just about as good against a Golem or Giants or Balor, for example, but against a Wraith or Medusa, the party is suddenly in much more trouble. You'll kind of have to play it by ear. It's difficult to give you a better idea because you haven't disclosed the nature or mechanics of the penalty for magic use.
As far as magic items, well, there should be absolutely no problem with that. As people so commonly repeat: the Monster Manual was not designed with the assumption that magic items would be available! That's partially why a Balor seems so wildly over CR (I've seen one die in a single round against a level 13 party, and two die in two rounds against the same party one level later). That means that, all things being equal, an average party should be expected to beat any appropriate challenge even if they're a bunch of melee characters fighting a Golem or Elemental!
At the end of the day, then, you can still use the game's built in Challenge system to build your encounters. The AC and HP values of monsters won't be a problem in and of themselves. What will be an issue is the monsters that have weird attacks or weird defenses, because the party will have few options against them, especially as their levels rise.