I'll be honest here: the mechanic of character development in terms of power is a staple of the RPG genre.
That's certainly true. But I think you're wrong in the assumption that leveling up is a necessary component of power-gaming and also wrong in the assumption that it requires magic to be a major game aspect.
What gamers want is a sense that at time x+a, their character is meaningfully more powerful than at time x. One of the reason why slow-progression systems (like stats that slowly improve over time) have tended to be less popular than punctuated benchmark systems (like leveling up) is that slow progression never let you feel meaningfully more powerful because "a" was too short and therefore f(x) was not much less than f(x+a). I suspect that's also why skill-tree systems like Diablo's have done so well, replacing the idea that all a fighter gets at the end of the level is +1 THAC0 (or was it -1? I can never remember AD&D's rules).
The question is whether you can make players feels meaningfully more powerful without leveling. The answer is probably yes. You give players improved equipment -- it need not be magical; a good horse, a fine suit of platemail, a honed sword and so forth can all be rare -- to satisfy the "oomph" factor, you give them new skills tied into meaningful plot points, etc. I think you could do enough to make it work without having to rely on experience.
The main advantage that seems to yield is that you can get players away from doing repetitive, stupid stuff. It frankly boggles the mind how long it takes RPG designers to get away from bad gameplay mechanics. It took the Japanese, what, like 20 years to ditch random, totally non-strategic battles prompted by invisible enemies on the map (and the mechanic is still lingering on). We're still doing fed ex quests? Including fed ex quests transparently designed to make you walk along the slowest, most circuitous route with the most loading delays? Players are still encourage (required?) to run out and fight the enemy even when the enemy is avoidable because if you don't keep starting meaningless fights on your own, you won't be strong enough down the line? Player still have to act as garbagemen taking all the crap they find on corpses and in trashbins (barrels, boxes, crates, etc.) in order to make enough money to get by? It just doesn't make much sense from a narrative standpoint (I don't mean a "making players read text or watch cutscenes" standpoint; I mean the narrative contained in the gameplay itself) or from a funness standpoint.
I agree it would be important to maintain the feeling that there's an obstacle at the start of the game that you cannot overcome, but can overcome at midgame (and so on). That's an integral part of the roleplaying experience. I'm just not sure leveling is the right way to do it.
This is now a horribly organized post, but I'll throw in a last thought. Experience (gold and items, too) is an incentive as well as a reward. If you give the player enough experience for rearranging a five hundred word list into alphabetical order, he'll do it, even if you put substantial loading delays into each rearrangement. I suspect you could get him to do it for +1 WIS in an AD&D game or +1 INT in Fallout. But you're a bad game designer if you're incentivizing unfun or frustrating behavior. You use incentives in games as a way of getting the player to learn fun new things in the game. How often has experience been used that way in RPGs? I would say perhaps not at all. You give rewards to the player as a way to make him feel a sense of accomplishment for what he's done. That's how experience is most often used in RPGs. But the rewards are given out almost thoughtlessly; rewarding a player for quests is silly because quests should provide their own reward (through plot advancement, roleplaying opportunities, and the closure of the quest's substory, and, most importantly through some meaningful effect on the gameworld), and the rewards for battles / traps / etc. usually come for things that are totally meaningless (clicking on a locked chest, clicking three times on an ogre, etc.) and not suitable for rewarding. To some extent, games get around this by giving meaninglessly low experience rewards for the meaningless battles / disarmings and obscenely high experience for killing bosses or completing quests (see, e.g., PS:T). But that just proves my point that there's no reason to give experience for that lesser stuff at all.
As I say, it turns a lot on the story you want to tell. But I do think there are better ways to do this than what we've currently got.
