Zelda is not an RPG. It's not even close.
One question that must be asked when assessing whether anything belongs to a particular genre is how closely it sticks to the roots of that genre. The roots of the RPG genre lie in the classic pen-and-paper RPGs such as Dungeons and Dragons. Being a Role Playing Game has less to do with story and more to do with stat building through monster encounters and various other mechanisms. Classic role playing also involved building a character from the ground up yourself within a certain set of rules and giving that character certain types of powers.
By that definition, it is possible for an action game to be an RPG (see The Elder Scrolls series, particularly Daggerfall), and for simplified versions--where, as opposed to building individual stats, you build
characters (JRPGs take advantage of this component). Classic JRPGs are simplified versions of Western RPGs (see Final Fantasy I or Phantasy Star II), but many of the elements are there.
JRPGs have strayed from the formula and that's skewed most gamers' perception of what an RPG is. You'll get lots of mixed up definitions, like an RPG is about story or about "playing a role" (whatever that means). While I have little affinity for classic RPG's and I love JRPG's to death, it's important to acknowledge where games stray from the formula. At its core, an RPG is about math. So how much math is there in Zelda? Most games involve stat-building of some kind. Even Pac-man has temporary stat boosts that superpower your character, and Super Mario Bros. features potentially permanent stat boosts through mushrooms and fire flowers. Stat boosting is a component of almost any game, whether it's a board game, card game, or video game, so that alone can't make something an RPG. Yet this is the only thing that really ties Zelda to classic RPG's. There can be no doubt that it is influenced by the basic ideas--go to towns, stock up on items, then head for the nearest dungeon--but at its core lies
action and neither classic
role playing nor
stat boosting.
Awhile ago I ran into a good article about why Zelda isn't an RPG. I still can't find it, but I found another one that I think sums things up well, in spite of its derogatory tone:
http://www.giantbomb.com/profile/kyle/zelda-is-not-an-rpg/30-15520/
Even games in which you "level up," like the Metroid-inspired Castlevanias or Zelda II, are not RPGs because the role-playing and stat-boosting are not their focus. The focus is item collection (essential to progress in the game, like Metroid), action, and platforming. Contrast this with a true action-RPG like the Tales or Elder Scrolls games, where the combat could conceivably be turn-based and (in the case of Elder Scrolls) is based on dice rolls--the action is secondary to the stat- or character-building.