Maybe something less built into the game, like a knowledge system. First time you go into Dungeon Crawl, you know next to nothing about good combinations, good weapons, aptitudes, gods etc. Play through it enough and you begin to understand and use those parts of the game better (not really the best example, but oh well).
The problem I've had with the knowledge system is that every game is a simulation of unknown depth. On a console, you can just push every button on every screen. On a PC, that's not quite so feasible. Roguelikes are the worst about playing for 20 hours straight and then 'Oh, if I push this key on this screen, this will happen (Elbereth, I'm looking at you). These things often have no ingame clues, so you are either reading the docs (spoiling and taking away the 'knowledge acquisition' portion) or acting randomly. (AKA I like it when the system EITHER tells you that you can do something or learning doesn't involve non-optimal experimentation) Acting randomly doesn't help when you have no reason to assume a command exists. Imagine a sidescroller where you push up to enter into a door that otherwise looks like part of the background. (fortunately you've only got ~10 buttons and can see the door)
*On a side note, I hated the old adventure games, because the USE THIS ON THAT command that worked never made more sense than the dozens of failed solutions I'd tried.*
That brings me back to the docs. Out of game Knowledge can be spoilerized, esp if it's not hinted at in the game (no other way to learn but raw, random experimentation) or involves heavy experimentation to decode the numbers (swords get a +1 vs zombies) that often fade to statistical insignificance. (OK look, it might help if I had a chest full of weapons of approximately the same strength and I new I was going into the graveyard, but in no other case does it help.)
\rant
Difficulty: Making such a game actually fun instead of a grindfest, and making it fun at lower metagame levels. Not sure how.
Perhaps exactly Nethack, only upon reaching a level 10 character, all starting characters start with +1 level.
All you lose is the first character level, which averages out quickly, (using D&D, start with 1000 xp, but level 5 it's meaningless) but allows you to start the game at a slight advantage.