If a character starts out weak and grows stronger, there must be some mechanical progression. I suppose you could play tricks like making the whole world weaker as the story progresses so that the player-character has no mechanical stat changes, but that's just beating the donkey on the other flank.
I dont think that how it works. Although your character gets "stronger", enemies do too and usually end up cancelling out this mechanical strength. In this case, the player is made to feel stronger. So even though the mechanical strengths are cancelled out, the fact that you are fighting what is precieved to be stronger enemies (the difference between rats and an ogre, for example) is what leads to this feeling of increased strength. Basically, its important how you perceive your character, and not the mechanics of your character per se (although mechanics can contribute to this perception). Personally, I dont feel like my character is "getting stronger" when I level up in most RPG's.
For me, the mechanics are more about letting me customise and define my character. The difference between going from a blank-slate to a wizard, rather than going from a weak character to a strong character.
I do believe this can be done with less emphasis on raw statistics and numbers. A game where character statistics were more fuzzy, and not the primary focus of the game is something I would personally consider potentially closer to an RPG, as it would make my character feel less like a database entry and more like a character. Although I do acknowledge that these statistical systems are often part of the more generally accepted definition of an RPG.
I see what you're saying in relation to a game that always throws a level-appropriate challenge at you. With a few caveats:
Imagine a game where you start out fighting Kobolds, move on to Lizard Men at level 2, Ogres at level 4, Trolls at level 6, Hill Giants at level 9. They're all humanoids, but they do slightly different tricks: lizard men swim and breathe water, trolls regenerate, giants throw boulders and golf-strike you with a big club. But basically they're all humanoids. I think ramping up the coolness of your enemies - larger, new special abilities - is part of showing that you're getting stronger.
Compare to a game where you do not always encounter a level-appropriate challenge. At level 1 you fight some kobolds, do well, and head into Ogre territory. You get spanked, basically. You go back to easier challenges and work your way up. Now at level 4 when you fight an Ogre it's much easier and you can win. And when you go back to kobolds for some reason they're much easier. Your character is clearly improving here.
I think when you feel like you aren't getting stronger it's because either your difficulty is set by the game (it always throws a level-appropriate challenge at you) or you are setting your difficulty by choosing to take on the toughest threat you can manage (you select a level-appropriate challenge that is as rewarding as possible while still being doable).
Imagine in a Final Fantasy game, not one which level-scales, where you grind in an area fighting slimes until you're level 10 when you were supposed to do the next boss at level 5. You're gonna steamroll that boss. But your momentum will quickly take you up though the game to areas where you're expected to be level 10, at which point you're probably level 12, and you slow down again. It's a choice between difficulty of the challenges vs. onerous grinding.