I'm going to call shenanigans on this. True, Rangers and Paladins did in AD&D gain spells, it wasn't until 8th level - just before name level as I mentioned earlier, and after a LOT of play. You're looking at getting 1st and 2nd level spells (and not too many of them) at the most by the end of a campaign. Add to that the fact that your clerics in AD&D (1e or 2e) have a MUCH truncated spell list that includes virtually no offensive spells until about 4th or 5th level (about 7th or 9th character level) and you're not going to see a whole lot of clerical magic outside of healing and status effect removal.
I'm sorry, I thought "low-magic" meant "classes didn't get access to spells", not "classes didn't get access to spells until high level, or the spells they got weren't blasty magic". Well by that measure, there is only one spellcasting class since clerics, druids, and illusionists didn't get access to blast magic either!
Interesting day when you learn a Paladin, Illusionist, Cleric, and Monk were a "low magic" party...
Add to that you have little to no magic item creation in AD&D (yes, yes, it could be done, but, it certainly wasn't as easy as it is in 3e), and the magic items you find are overwhelmingly consumables.
I agreed on that.
Now, you could certainly jack up the magic level. You mention Tomb of Horrors or White Plume Mountain. Both Gygax modules which are seriously Monty Haul, but, besides that, both very high level modules as well. Start looking at modules like Secret of Saltmarsh, Cult of the Reptile God, Isle of Dread, or the A series modules and there aren't all that many magic items in there. It isn't until you get into the high level stuff, particularly the high level Gygax stuff, that you see very high magic. But, then again, as far as magical creatures go, remember, most critters didn't have magical effects. Again, you mention demons - something you generally don't see until name level. Drow is another example of high level monster as are Mind Flayers. Get in to the stuff you would typically meet from levels 1-9, trolls, giants, orcs and humanoids, maybe some of the lower end undead, and various giant animals, and you don't see a lot of magic.
I mentioned them as magical LOCATIONS. Magic portals, magical traps, strange pools, etc. Not purely on the amount of treasure, but there was definitely some.
Now, lets ignore the high-level stuff for a moment: I grabbed three first-level modules I own (T1, L1, U1: Hommlet, Bone Hill, Saltmarsh) and scanned each for magical items (conveniently, they are bolded in most of them). This is what I found...
Hommlet: The least amount, but there is a half-dozen potions, an elven cloak, and Lareth's staff of striking if you best him.
Bone Hill: Most of the important NPCs (including the bugbear chieftain and several mages) have potions or +1 gear. (Rings, splitmail, or weapons)
Saltmarsh: The House has two rings +1 and platemail +1, and a couple NPCs have +1 swords.
Low magic? Well, not common (due to level and challenges faced) but certainly 4-6 items per module.
Good grief, look at the change to dragons. Dragons in 1e might not even have any spells. By 3rd edition, every Elder Wyrm is an Archmage. Demons go from having a small handful of spell abilities to having a shopping list. On an on.
And ironically, 5e dragons don't even have spells (unless the DM uses a variant to give them a handful) and demons often lack that. Guess you could say 5e dragons and demons are lower magic than AD&D ones.
And that's my point. You could play earlier D&D as high magic. Not a problem whatsoever. Most of the magic would come from items. But, you could very easily play 1e or 2e as pretty low magic. One or two items per PC by 8th level, wizards weren't needed - fighters and fighter types were such damage kings that wizards were pretty much baggage until about 6th level. The primary source of magic in the game, at least on a session by session basis would be clerics.
Oh, so low-magic equals no MAGIC-USERS/MAGES/WIZARDS, not actually "no spellcasters" or "no magic items" or "no magic-using monsters". Gotcha.
Not that it had to be played this way. But, it very, very easily could. It's 3e that blew those gates wide open - bonus spells for casters, any class that gained spells gained them MUCH earlier - Paladins go from gaining a single 1st level cleric spell at 9th to gaining spells by 4th level, and gaining bonus spells for high stats. Never minding a hugely expanded spell list to choose from.
So lets agree on this: 3e was the "Magic is King" edition and certainly not what we're striving for. But does 5e? Well, its a little higher than AD&D (due to at-will cantrips and rangers/paladins getting spells early), not quite as high as stock 4e (thanks to 4e's over-reliance on +X items to keep the math working) and nowhere near as high as 3e. Heck, 5e has been out for a year and a half already and we have a dozen new elemental spells and four new cantrips, so we aren't even facing hugely expanding spell lists.
But almost none of this proves to me you need a warlord to make nonmagical gaming viable. By your own admission, AD&D was "low magic" but still allowed Clerics, Paladins, +1 platemail at first level, potions of healing, etc. Doesn't seem like the warlord is adding much except just another choice of class.
So again, I'm not seeing a NEED to have a full warlord class. I'm seeing a DESIRE for one, but no gaping hole left open by its absence, unless AD&D suffered from the same hole (and right now, two people have told me 1e did low magic well without a warlord class, so I'm guessing it didn't).