I think it would very much work. Basically this is the endgame of any MMORPG as I see it, without the need to grind your way up to max level.
Something I really like the sound of, grinding mindless AIs for exp is not fun.
EVE online doesn't have levels and not experience as traditional RPGs have. In the end though you still have to grind currency in some way to be able to buy new skills to progress.
And as said, Guild Wars put a lot of focus on chosing skills. Sure there was leveling, but no real weight was put on that, it didn't take much time at all when compared to WoW or the like to reach max level.

Imagine: characters with static skills, and the challenge is how best to use the skills they have to overcome what obstacles the game throws at them.[/quote]
Isn't this just like any other action/adventure or tactical (e.g. commandos) game then?

A genre is defined by why people play it. http://penny-arcade.com/patv/episode/western-japanese-rpgs-part-1

I would imagine that there should be some sort of progression. You could pay trainers to teach you skills, but they can't increase your stats. You can only get the strongest weapons and stuff from dangerous dungeons, thus making both the weapon more valuable and encouraging the designer to make the dungeon more difficult. (note:There is a big difference between legendary and normal, and normal cities only have normal stuff.) Your stats improve over time to match your playstyle, but it would be a smooth one that you wouldn't notice unless you either noticed the visual cues (i.e. your fireball is bigger) or you actually tested it out. As such, the focus would be on increasing your power in other ways, and getting stronger is a side effect not worth grinding for. That would also require that the game itself would be fun.

Therefore, there would be a sense of progression, but you can't grind for it. Instead, you would be scouting the wilderness for a non-generic temple, and need to use your variety of skills to outsmart the gaurdians. Alternatively, you could do sandboxy things like http://www.lofigames.com/index.php?option=com_content&view=article&id=84:quests-quests&catid=38:game-design&Itemid=55

I think skills/levels should be earned through experience not experience points. Characters who pick up a bow and arrow should get the idea of how to shoot it but shoot it badly until they

1) Watch another character shoot it better (like Metroid data analysis system) increasing the visible skill of the character
B) Read about how to shoot it better and practice (meta game tutorial for skills)
#) Face an enemy and learn from the enemy's skills with that weapon (surviving the encounter inceasing the skill)
four) Player properly compensates for the designed failings of the characters use of the skill thus unlocking the characters "hidden talent" for said skill
FIVE) Any other creative interactive system to connect the player to the experience of learning that skill
sX) All of the above
upsidedownL) Decide not to use the stupid skill because its not how I play anyways

Experience should only be counted by the player not by the game HUD. Hide the data, show the game. Skilled players will count and unlock the games "algorithmic structure?" before long anyways and unskilled players will just enjoy watching their character change and grow.

The way to keep this system from becoming overwhelming is to give more linear and structured design at the start of the game like a shooter (call of duty teaches you your weapon choices before it demands you to fight with them). Show a variety of choices for the player to explore, hint at a bunch that they will find down the road and make this training section an option for veteran players to breeze through and ta da. Sexy foil RPG experience without grinding!