I do not see any good reason to say that there is some privileged usage of "RPG". One person says that story and immersion matter; another says that character definition and progression matter. Both are right - in their own idiolect. There's no need to disagree here. Accepted terminology for genre classifications just aren't that fine-grained. Better just to realise that different people will use the term slightly differently. To the extent that there is a substantive debate to be had (and often there isn't), we can resort to neutral terminology.
And yet, the fact remains that stats (as used to define a character and allow for progression) is an essential feature of all RPG video games. Everything else people commonly mistake as essential features (storyline, etc) may add a lot to the game, but are certainly not vital. That's why you can find many examples of RPGs without storylines, but will have a hard time finding a single one that doesn't use stats to define characters.
Exactly - now does the game keep track of this? If yes, that's an RPG. If not, and you have to pretend these characteristics are in the game - then it's not an RPG. Sure, loads of people here make-believe in their games, but I don't, plus that's not a good way to define an RPG. You have to judge a game by what the Devs have built, not what is built in your mind.
TESFanner gets it.
In order to define my character through actions, there has to be consequences, and to have consequences, you need stats. For instance, if I go upto an NPC and hit them, will that NPC take a hostile tone towards my character in future? Will other NPCs who witnessed the action regard my character as being dishonorable? Sure, I can "imagine" what impact actions are having on my character's persona, but it's not the same.
In the original RPG (paper & dice Dungeons & Dragons), the "game" didn't keep track of anything; the players and dungeon master did all the work. The math and dice-rolling were never considered part of the role-playing. Playing a role is all about stepping into your character's boots; speaking, thinking, and acting in-character.
Table-top roleplaying and RPG video games work differently. It annoys me that people keep trying to make the comparison.