Some champions don't deal magic damage, but all champions deal physical damage.
This is obviously because all champions have the ability to use basic attacks, and basic attacks deal physical damage.
.. but, should they?
There are lots of basic attacks that are obviously physical. Champions that use natural weapons, swords, staves, axes, hammers, a scythe, guns, bow and arrows, crossbows and bolts, ..
Many magic based champions "throw" magical bolts of energy from their hands as basic attacks.
Shouldn't these deal magic damage?
I understand that this was most likely done initially for simplicity, .. but I think we should be beyond that at this point.
And I think it would also be important to separate the distinction of "attack damage" from physical damage in the same way that we seperate "ability power" with magic damage. Basic attacks, like abilities, should be able to scale with AD and/or AP, and still deal either magic or physical damage, or in some cases a mixture of both.
Edit: Literally all I am suggesting to change is the type of damage output through basic attacks.
The way basic attack damage is calculated would not necessarily change, however this does also open up that possibility.
For example, Syndra has a Base Attack Damage at level 1 of 53.9. Her basic attacks (without any additional AD) deal 53.9 physical damage. I am suggesting that she should instead be dealing 53.9 magic damage.
Buying AP would not increase her basic attack damage. Buying AD would increase her basic attack damage, but it would still be dealt as magic damage.
Why? This would make a purely magic damage champion weaker to enemies who have MR. As I pointed out in the title, there are champions who deal no magic damage. These champions are weaker against enemies that buy armor.
NOT ALL MAGES SHOULD HAVE THIS DONE TO THEM! But, I think it would be reasonable if some did.

-- His auto attack is sort of a breath weapon. Would his breath weapon deal magic damage? I vote Yes on Aurelion Sol.
-- In human form she has a ranged magical auto attack, but in spider form she uses melee attacks. So maybe her autos in human form can do magic damage, but her spider form autos continue to do physical damage?
-- She's in a really strange place. Orianna doesn't shoot a magical blast as her basic attack, she throws a projectile (which would be physical damage), but her basic attacks already scale with magic damage.
-- Her basic attack is throwing rocks, which are projectiles, but throwing rocks as Taliyah is a spell because she's the Stoneweaver. I would vote Yes for Taliyah.
-- Right now his basic attacks actually do magic damage (80%), but his basic attack is a bullet. Corki can stay the way he is, since his passive is "Hextech Shells" and imply that his bullets are in fact magic.
-- Ezreal is literally a mage whose spells do physical damage. So even though his basic attack is a spell, it would deal physical damage anyway.
-- Though an AP-scaling champion, Heimerdinger throws objects instead of casting spells or firing energy blasts like his magic damage turrets. I would vote No for Heimerdinger, his should stay physical.
-- Kai'sa launches some sort of dark bolt, which is a spell like basic attack. She also scales with AP, but scales with AD too, and some of her abilities that launch dark bolts scale off AP and some off AD. There is no definitive answer.
-- Deals magic damage, but he throws a shuriken instead of casting a lightning bolt. I would vote No for Kennen, his should stay physical.
-- We've determined that his acid spit abilities deal magic damage. Would that mean Kog'maw, whose basic attacks are him spitting acid, deals magic damage on basic attack?
-- Throws a spear as her basic attack, but her Q is also throwing a spear that does magic damage. This seems like she should still do physical damage on basic attack -- her short range spears are normal spears that deal physical damage, but her long range spear she throws for Q (a different kind of spear -- note how it has four times the range) is enchanted and deals magic damage.
-- His darts do magic damage over time from the poison. But that's from poison applied to the dart, not the dart itself. The dart is physical damage and the poison on it is magic damage. I would vote No on Teemo, keep it physical.
-- Zilean throws a projectile, and it's not like the projectile he throws for his Q. I vote No for Zilean -- keep it physical.
is the only champion whos AA deal magic damage instead of physical
after passive