Before I start, here's the reason that the definition of a roleplaying game is debated; being the father of modern roleplaying games, all mechanical elements of Dungeons & Dragons are popularly assumed to be roleplaying elements. Of course, the mud in those waters is that Dungeons & Dragons is an offshoot of military tabletop games, so many of its elements were never really intended to inherently be roleplaying elements.
With that out of the way, I'll break the definition of roleplaying games into its two parts, starting with roleplaying. In the most concrete instance, roleplaying exercises, the player acts out a character as a referee lets him know what the character can and cannot do. As the player decides the actions for the character, he learns how the decisions change the scenario.
On a parallel note, as the player affects the scenario, he also affects the narrative, hence the importance of plot in roleplaying games. The three acts of a story are answers to the three questions, "who is trying to accomplish what," "how are they trying to go about it," and, "what is the result?" All roleplaying is done within a spectrum between player freedom and referee control, but generally speaking, the more options that the player has for Act 2, and the greater the differences in effect that the options have in Act 3, the more that he has roleplayed.
As for "what is a game," it's a recreational test of skill. That one isn't hotly contested. A roleplaying game, more or less, is then test of a player's ability to change a story through making decisions for his character.
Going back to Dungeons & Dragons, yes, all of it serves its roleplaying, but not all of it is necessary for roleplaying itself because Dungeons & Dragons seeks to tell a specific kind of story, namely the Hero's Journey. Character levels are not necessary for changing a story, but they do define how much power the hero has acquired, allowing the referee to quell most arguments. Of course, it's not uncommon for a referee to want to prevent player interference in his meticulously crafted story, but unfortunately for him, that femme fatale was no match for my murder hobo.