I guess Pac-Man is an RPG then...
Hyperbolic much? What role is it you're playing in Pac Man, professional athlete?
This is, as far as I can see, a reason for there to be a moratorium on discussion of the definition of RPG. A character sheet was a part of what it meant to sit down and play D&D, of course, it also made it easier to keep track of who my character was, what they had, what skills/feats/spells etc. Of course, that doesn't preclude the fact that I may have been an Elven rogue/wizard, or a dwarven warrior, or any of the various class/racial combinations that came later.
So unless you're a cowboy, running around shooting bad guys, or good guys, all day, I'd say that RDR certainly qualifies as an RPG. Pac Man, for all the hyperbole of "you disregard my narrow world view of what an RPG is, so I'm going to lash out in the most inane way possible to say that all games are RPGs, so there", probably followed immediately by sticking one's tongue out at the monitor for emphasis, does not. An argument could be made for Mario Bros, I guess, since there is at least some kind of story element involved, but running around in circles eating pills and ghosts doesn't really equate to story. You might have had better luck going with Galaga or Space Invaders...