I've spent some time thinking about this question of why it seems so strange to see a game with no in-game leveling as a "roleplaying game." As I did, it occurred to me that I may actually be adding to the confusion by using the word "roleplaying" in two ways.
First, there's the big sense of the word: when you play an RPG of any kind, when you control a character that's not you, you're playing a role -- you're roleplaying. In this sense, it doesn't matter what else you do (leveling, chatting, etc.); as long as you're controlling a character who's not you in a roleplaying game, you're roleplaying.
But I've also used the word in a more limited sense to describe a kind of player who really gets into a character, who is careful not to discuss the outcome of the Bears-Ravens game or otherwise break the magic circle of the game's fiction. This kind of "roleplayer" is someone who plays a MMORPG specifically to interact with other players in character. (I actually equate this style of gameplay to Bartle's "Socializer" type as well as the "Narrativist" style in the GNS model.)
To try to make this distinction more concrete, the former kind of roleplayer is someone who comes to a MMORPG for the MMOG part and "roleplays" only in the sense that there's no way to escape the RP part. Meanwhile, the latter kind of Roleplayer (I'll capitalize this type for clarity) comes for the RP features and merely tolerates (sometimes) the "out of character" MMOG behaviors of others who are focused on rules-based gameplay.
Where that distinction fits into this discussion is that players with these two styles look at character advancement differently... and to make life even more entertaining, there's at least one and probably two other styles who have their own ways of defining "roleplaying" (in the larger sense). Explorers like myself, for instance, look at playing a character as a way to explore game systems, rather than as rules-based competition or story-based interaction.
What all this means -- and we've entered the Land of Theory here, so you're free to disagree, but as theories go I think this one holds together reasonably well -- is that all these types of gamers look at leveling differently.
The person who comes to a MMORPG for the gameplay (usually described as the "Achiever" Bartle Type) sees leveling as gameplay. For them, an action taken to advance a character in capability isn't a prelude to play, it is play. It's an integral piece of the "..G" part in "RPG". Which means that calls like mine to make an RPG without leveling only sound like "I don't want you to have as much game in your game," which to these folks is obviously crazy talk.
Where I come into this is my theory that Roleplayers (Bartle's "Socializers") and Explorers are less interested in gameplay for the sake of gameplay. The Roleplayers are looking for stories to tell and be a part of, for narrative, so dropping character advancement is actually (IMO) kind of a plus for them. By giving them characters with all possible abilities, their opportunities to tell interesting stories are maximized.
(One exception to this is the "coming of age" story. This would be a case in which Roleplayers would want character advancement... except that even in games that have it, characters don't age. Advancement in current MMORPGs is simply about gaining more power, and that change is never part of a meaningful story about the player's character in which the outer changes are intended to serve as a mirror for the more important changes that define who the character is in his or her heart. So there is a way that MMORPGs could offer character advancement that Roleplayers would enjoy, but no current MMORPGs actually do this.)
Explorers, meantime, have a foot in both the worlds of Game and Story. For them, these two aspects of a MMORPG come together to create systems to explore. In this worldview, leveling might be a system to explore once, but once it's been seen (especially in a class-based system where everybody experiences exactly the same progression) it actually becomes an impediment to gameplay because it prevents the Explorer from being able to fully explore the game's systems.
As an Explorer, that's probably where I get my aversion to in-game leveling. And it's why I keep bringing up Traveller: it's evidence that an RPG without character advancement has worked, and can work.
It's not about just pushing Traveller. I like Traveller, but I'm not a fanboi blind to its faults -- it's just an example of an RPG without in-game leveling that has been commercially and critically successful. Demonstrating that this is possible is the only reason I bring up Traveller. And that in turn is only to make the larger point that (for Explorers in particular) games where you play a character who doesn't have to level up are not only RPGs, they're a lot more fun than RPGs whose core gameplay is about "forcing" you to level up!
OK, having posited these different types, let me now see if I can use Traveller (in its tabletop RPG form, since it doesn't exist as an MMORPG -- unfortunately!) to show you how someone from each playstyle might react to the absence of leveling. In other words, what there is to do in an RPG without in-game leveling.
Traveller's key features (IMO) are its very detailed character creation system, its thousands of different worlds, its intelligent backstory with political, sociological and economic depth, its generalized task system that's easily adapted to handle novel situations, its well-defined starships, and its broad array of roughly 100 skills. In other words, it's a very balanced mixture of gameplay, story, and setting.
So an Achiever is likely to focus on using skills that allow the character to grow in power. Traveller offers numerous combat and economic skills, and even packages them in the Army, (Space) Navy, Marines, and Merchant templates that can be used during character creation. Whether on the ground or in space, Traveller definitely accommodates a player who likes a good fight or who wants to try to become a merchant prince in one of Traveller's megacorporations. The lack of character advancement during gameplay would probably seem strange at first to an Achiever used to MMORPGs, but a GM can easily provide adventures that offer nearly-constant action and rewards of various kinds. Rewards for Achievers in Traveller would indeed probably include advanced gear (and there's some very cool gear in Traveller) and, for the economic Achiever, the chance to become rich by traveling among the worlds with the right goods for sale. (Freelancer captured something of this style of play.) In time, however, it's possible that this might pall for the MMORPG-trained Achiever, since Traveller is more about going places and doing things than about collecting stuff.
Something like that also applies to the Roleplayer/Socializer. There's less content for this style of play in Traveller primarily because it's not a massively multiplayer game world like a MMORPG -- "socializing" would be just chatting with the other people in the group. With its rich backstory and well-defined alien races and worlds, however, Traveller does lend itself to exciting storytelling. Players in Traveller find it relatively easy to take on the persona of the character they've created, then to interact in interesting ways with the denizens of the Imperium. Traveller adventures are always wrapped in some interesting story, often giving players opportunities (as part of the story) to affect the game world in meaningful ways. Roleplayers tend to like that; it makes both the gameworld and characters feel more real. Still, as noted, Traveller's focus on action means that there aren't as many features to support character development as Roleplayers might like.
But Explorers, now... Explorers love Traveller. It is an RPG to them because they are playing characters, but the focus on playing a character in Traveller that Explorers have is the setting -- they're out to see the galaxy in all its variety. They'll be doing so as a character in that fictional setting, so it's roleplaying in the "small-r" sense. And visiting strange new worlds and seeking out new life and new civilizations very definitely mean having exciting adventures in the unknown -- sometimes combat action, sometimes intriguing interactions with NPCs, sometimes puzzles to solve, but always something fun to do. But ultimately Explorers live in between the RP and the G parts of Traveller as an RPG: they're playing characters in a game in order to explore the many cool systems of the setting.
All this is a bunch of text, but I hope it provides some insight on how it is that I (and, let's be fair, plenty of others who've played it) certainly do see Traveller as a full-up RPG even though characters don't gain ability levels in the game. I hope it also shows how a game can very clearly be an RPG without in-game leveling, since "a game that lets you play the role of a character" is what seems to be the best definition of an RPG, rather than a particular game mechanism (no matter how apparently useful) for increasing a character's in-game abilities.
In the end, "What is there is to do in a roleplaying game that doesn't let you advance in ability levels?" is a question that just doesn't make sense to someone who's played a complete-character RPG. What there is to do is exactly the same kinds of things that we do in MMORPGs now -- combat, commerce, exploration, socializing -- the only difference being that in a no-leveling RPG (such as Traveller), you're not restricted by your character's abilities in doing any of those things. You can just go do them. The content is parsed out by the GM as whatever encounters you happen to have in any play session.
(Side note for Traveller purists: Yes, I know there actually is a way to gain skill levels in Traveller... or at least, MegaTraveller and beyond. However, this process takes so long and the chance of gaining a single level in anything is so subject to random chance that it's just not a meaningful part of Traveller's gameplay. Nobody plays Traveller to level up.)
In the end I think the word "goal" is the most important for understanding how different people can look at a no-advancement RPG and see it very clearly as an RPG. If one considers leveling up during gameplay to be a required goal in an RPG, then sure, obviously a game without leveling doesn't look like an RPG.
But not everyone sees leveling as a goal in and of itself! To other kinds of gamers, leveling is not a "want to," it's a "have to." It's something you're forced to do in order to have the skills to enjoy the kind of story-based or system-discovery-based gameplay you prefer. Which means that for some gamers, getting rid of leveling is actually the removal of an impediment to having fun, not a reduction of fun.
Whew! I'm not assuming that I've changed any minds with all this, but I am hoping I've explained this perspective on RPGs-without-in-game-leveling at least well enough so that the non-Achiever perspective -- which says that in-game leveling is a problem to be corrected, not a goal to be achieved -- is somewhat clearer.