First. Gandalf was a powerful caster. He had the magic, he was just not overt with it. He would've used stuff like divination spells or abjuration spells to buff himself or the party. I.e. stuff that isn't flashy. This is because he wasn't really allowed to use his full strength (banned by basically the gods). The one time he almost does this is when he first comes back to life as the white wizard and nearly kills Aragorn and company due to being confused in the books. Second. Magic in middle earth *does* exist. There *are* wizards, druids, clerics, etc. They just pale in comparison to the named wizards who are in fact demigods. Anyone who tells you otherwise is wrong. Even the movies reference this, where the council first writes off Sauron coming back as "just a necromancer" in the hobbit. The point of Sarumon's line there is that they (being gods) have no reason to concern themselves with a minor mortal threat.
...middle earth soapbox aside, there are a few options:
1) Work with the DM to play off a class's spells as something else. Ranger healing is herbs, entangle as traps/snares, paladin spells as sword techniques or first aid, sorcerer spells as Magic trinkets or gadgets, there is a lot you can do.
2) Allow the player/DM to handle the spells as a roleplaying opportunity rather than a ban. So they are a wizard. Great! How long do you think an openly casting sorceress or warlock would have lasted in the Salem witch trial days? Drive home the fact that magic is rare. Have literally everyone be afraid of the player who is flinging fireballs, or treat the player as a prophet when they start healing people or reading the future. The party will not like the attention longterm. Sure it might be cool at first, but what happens when the evil noble lord hears of this very real threat to his law and order? Or when an entire religion starts cropping up around the cleric and his actual god gets pissed? There is a plethora of ways to handle this.
3) If you must be needlessly strict on "no magic", you should probably play a different system, as literally every class except barbarian in 5th has a magical subclass or magic by base. You would be banning like 90% of all player options depending on how one interprets things. Still, if we must go down that rabbit hole, I would suggest totem barbarian with ritual caster. Make yourself a crazy shaman sort of character. Or battlemaster fighter. It really is the closest to a "tactician", which is what the caster archetype would be in a non-magic game. There is also the artificer if the DM allows it, and the mastermind rogue, or the monk.
I agree with the idea of magic initiate, but question what the real difference is between the feat and a Class level in a magic class. Why would the feat be allowed but not the other? It is still using actual magic.
