I did this with Savage Worlds for a psionic character. If you are not familiar with Savage Worlds, there is a much lower number of spells in the systems and you give them magical trappings. So instead of having to pick through 9 thousand minor variants of magic missile and fireball from the Spell Compendium, you pick Bolt / Blast and define all the look and minor tweaks. Extending the trapping concept to the systems skills and Edges (~feats) really enhanced the experience for me. At the end of a campaign, another player said they had no idea if my character was casting a spell, using a skill, or an Edge whenever I declared an action. That was very satisfying.
Making fighter skills and feats "magical" may not fully jive for most people, but the concept certainly can work - ie, reskinning. Perhaps Dwarven fighters, while having access to the same stuff, have different descriptions for how the result occurs ("I hit him Dwarven-style!"). I again did this in Savage Worlds to make what was equivalent to a Psychic Warrior from 3e. The PC had no spellcasting abilities from the system at all, but all the skills and Edges (feats) all were based off the concept of the PC being able to see a couple of seconds into the future (Jedi without the JarJar). So Edges like First Strike (a free attack on someone comes up to you), Block (like Dodge in D&D), Initiative Edges, etc are all standard combat stuff that takes on a new feel by providing a theme/trapping/reskin.