I would really like to play a Role Playing Game without any kind of XP mechanic. I think it'd be really cool to play through an epic storyline that my character came through about as strong at the end as it was at the beginning.
An alternative to this is making the environment more complex: changing what the player has to do instead of what he can do. This has been done by some games (Super Meat Boy comes to mind right away), but I don't think it works very well with the tropes of RPGs. The canonical RPG is the hero's journey, and that story really calls for improvement in the hero.
The one game that I can think of as having an excellent portrayal of the hero's journey without character improvement is Journey.
I think that that kind of progression is a more accurate indicator of a) whether the player is ready to handle the complexity that the new ability brings, and b) the value the player has received from the game, so far (if we're dismissing the notion that time spent is necessarily proportional to value).
Note that you can have the character-improvement mechanic in more than RPGs; a game like Half-Life introduces weapons, equipment, and new ways to manipulate the environment as you progress.
(Or Heavy Rain. Or every point-n-click adventure ever.)
You can skip character development altogether in the Mass Effect series (especially if you lower the difficulty and enable autoleveling). Only the first one requires you to increase a member's e.g tech skills to unlock some devices.
I played the first one without using basically any skills but my player sharpshooting abilities, occasionally upgrading armor and guns, more often than not for the sake of looks.
Telling stories, Resident Evil or Gears of Wars also come to mind, but I'm not sure that's what is asked here.
If someone wants something more freeform, maybe Skyrim, and dialing down the difficulty level will make a warrior's adventure possible (challenging even) without caring about the levels. A thief might be harder (without any points, I manage to stay covert, or pick master locks with patience, precision and a dozen lockpicks, but purse stealing is still a dice roll), while a wizard will be fundamentally limited in available spells unless he increases magicka.
Therefore I suppose here's the point: a game purposely designed on emphasizing on the player's skill (like lockpicking a master lock) instead of a virtually progressing one is something I would certainly like to play.
The original site seems to be down at the moment, but fortunately, someone put it on Flickr.
Great storyline and writing, with no XP or grinding or anything of the sort. The player does find different - not necessarily better - weapons, and the only sort of 'levelling up' you do is yourself getting better at the combat mechanics.
Another is to limit the communication to human terms. Maybe you occlude all knowledge like jcromartie says, or maybe you realize that nobody ever feels like they have 18.6 strength. They feel weak, strong, or very strong. They feel nimble, graceful, clumsy, dumb, quick, lethargic, injured, smart, etc. Color gradients might be a non numerical way to give fuzzy information about ability. Your character is not a precision machine (unless maybe you're playing mechwarrior)
The roots of the RPG genre are in games like Dungeons and Dragons where character progression (through gaining XP and levelling up and then choosing perks/skills) were how you added additional definition to your character beyond the things you chose at the start (like name, race, etc). Modern RPGs have expanded on this with complex skill systems and relationship systems and such, but almost all of that still sits atop the foundation of character growth through point rewards during gameplay (experience, gold, etc).
1. You start weak and finish weak. This gives you games like "I wanna be the guy", which build player skill, but I haven't seen this in RPGs. If the player gets noticeably stronger and then weaker along the way, the part where the character's powers are taken away can make the player feel cheated. (Not always: see e.g., the last fight in Ocarina of Time.)
2. You start strong and finish strong. Everything is easy and boring, unless you are depowered along the way and have to claw your way back up. See Metroid Prime (1 or 2) on the GameCube, or Wonder Boy III: Dragon's Trap on the Master System (or Dragon's Curse on TG-16). Usually the strong start is used to ease the player into the game, so that it's harder to fail while learning the controls and patterns of the game. Regardless, you still have a definite progression: either of tools, stats or something else that means you can go to places you couldn't before.
Wonder Boy III is an interesting example, because although you start with the best armour and weapon at the start of the game (which you then lose), the various forms that the player takes (mouse-man, hawk-man, &c.) give the player a different kind of power than the one that was removed: flexibility of movement as opposed to better offensive/defensive stats.
<aside>I have read about an interesting house-rule for D&D 3.5 called "Epic Six", which gives a similar result but not using the mechanic you suggested: http://www.enworld.org/forum/general-rpg-discussion/206323-e...
Basically, characters do not level up beyond level six, but gain additional feats every 5000XP which provide various small bonuses. This means that the players still get more powerful, but they don't scale up into the world-destroying powerhouses that you get at high levels.</aside>
I don't think that getting rid of XP means that you should throw out the whole concept of power progression in an rpg-like game. You may as well tie power progression to items or other things that will happen along the way. If you have an XP system (with power progression tied mainly to XP), then you as a designer need to match XP progression to story progression. If you don't, players either need to grind (yuk) or everything's too easy because you're levelling too fast (snore). Why not throw that out and go with the metroidvania-style of getting more tools to solve your problems? Metroid did this especially well because if the current fight was too hard, you could backtrack and explore for more energy tanks, missiles and so on so you have more resources at your disposal.