Then there's the ubiquity of magic.
Magic is ubiquitous among classes in 5e, sure: every class has supernatural powers, no exceptions - Ki is explicitly magical, Fighters & Rogues can cast spells, Totem Barbarian use them as rituals and their rage comes from a supernatural source. But it's not ubiquitous in the wider world, unless you assume character classes are - magic items are comparatively rare, supernatural monsters or the DM's to place in whatever frequency he sees fit, or choose not to use at all.
It's not as bad as 4E (where IMHO everyone had supernatural abilities) but it's still too common for a low magic world.
Then your opinion is at odds with the facts. In 4e, there were several Sources, only one of which, 'Martial,' was explicitly not supernatural, and none of the only-4 classes that depended solely on that source was able to fill the 'Controller' Role, so the non-supernatural side was still pointedly under-served. Still, it was the high-water mark for D&D as far as support for and balance of non-supernatural PCs was concerned. (For the record, late 3.5, with the highly-customizable, non-supernatural fighter and Rogue in the PH, followed by the Knight, Scout and the beefed-up-fighter Warblade just before the ed closed, came in second in that sense, and 5e, with /every/ class having some supernatural powers, and only 3 having sub-classes nominally free of them, with all of those laser-focused on DPR, has arguably defined a new low in that regard.)
But over the history of D&D it does seem like there's been more and more of a move towards the supernatural/magic classes and builds. That's not necessarily a bad thing it just may not work for every campaign.
I think it's more a circle than a straight-line trend. In the early game, when a sub-class called for some ability, spells tended to be thrown at it to open up competence - thus spellcatsing rangers, for instance. Similarly, things that could reasonably be accomplished without magic, like lopping off a limb with a slashing weapon for example, could, for convenience, I suppose, only be accomplished with a magic item - the sword of sharpness, for the same example. As the game evolved through to 4e, non-magical options became more and more capable, and magic & non-magic, alike, became less niche-protected.
5e has returned to a focus on PC magical abilities as their prime defining and most significant practical abilities. Skills aren't gone, but they aren't niche-protected 'special abilities' like they were for the Thief in the classic game, nor able to do much that stands out; non-magical combat is back to just doling out damage as rapidly as possible. FWIW.
I agree with most of this except the bold part. IMO, it is very easy to play 5e with low-magic. I would even argue from monster stand point it works better in a low-magic world. Now, you have to restrict things which some DMs don't like to do, but the core of the game functions wonderfully with low or non magic.
It very much depends on what you mean by 'low magic.' High-magic, spellcasting PCs adventuring in a low-magic world with few to no magic items to be found? 5e works fine. A low/no-magic party, regardless of world? Not s'much.
How do you go about doing it? Just ban wizards/sorcerers/clerics/druids and several subclasses?
I'm curious because I was thinking about trying something along these lines someday.
You could reduce magic on the party side by removing full-casters entirely, sure, leaving you with half- and third- casters, and every class still able to use magic, just not as powerful magic. You could reduce the availability of magic by removing cantrip & rituals, Warlocks, & 1/2 & 1/3-casters and substantially reducing spell slots for full casters (1 to 3 slots of a level equal to their highest-level spell, only). Or you could re-focus magic to be more genre-conformal by removing slots, instead, but keeping rituals, cantrips, and, for the most potent casters, the odd attack cantrip at full power.
What you can't do is remove magic entirely from the game and still have it function, the very few, very limited, overly focused non-supernatural PC options just aren't up to it.
The Template idea might very well help with that, giving PCs another source of missing out-of-combat and support contributions.
I think it would be really hard to design characters like that. You're basically creating Category A puzzle piece, and Category B puzzle piece. So that would mean that you would have to ...make sure that the pieces fit together and that they are relatively equal. ...
I don't think you can design characters in that way using your new template. It feels more like 'Linking' mechanics as a posed to 'Stacking' mechanics.
'Linking,' if I follow, could work better than Stacking (which has more potential for abuse).
For instance, you could have three puzzle-pieces - the existing Background & Class, plus a Template - but focus each one on a single pillar. Class could provide the character's combat-pillar focus/role & effectiveness. Background could provide his social status, context, and interaction capabilities. Template, then, by default (and 'woodsman' serves as a good example, here), could provide his competence & theme in the exploration pillar.
I like the direction you're going with Backgrounds. Backgrounds are there to "tie" you into the world, expanding on that would be good. You can have...Fore?ground. Basically a "new Background" when you enter a new Tier, a sort of "Checking in" with the world.
Sounds interesting...