The main problem of game-ending character death stems from the player's perception of the return on their investment of time and effort. The more time and effort the player puts into improving a character's intrinsic assets (abilities, knowledge, relationships, progress), the higher the perceived cost of the loss of that character.
So the key questions related to permadeath are all related to the amount/number of personal assets that a character can accumulate in a game:
- How long does a typical game last?
- How much can a player invest in a character? (In other words, how much "character" can a character have?)
- Can accumulated player character assets be transferred upon death to another character?
1. Make the game so short that reloading feels acceptable. In a game that's short enough to minimize the sting of permadeath, it probably won't be possible to have a character who's well-developed enough to be interesting. But very clever writing might make this possible.
2. Minimize the number and importance of assets that the player character can accumulate. Multiplayer shooters take this approach. Again, the "character" is not developed as such. Characters are essentially vehicles intended to be occupied temporarily; they're never given names or opportunities to collect assets that are intrinsic to them as people. (Players may be awarded badges for achievement, but player != character.)
Another example of this would be a game I imagined a few years back (before Spore was announced, incidentally): you'd be a cellular lifeform in a tidal pool trying to support the development of a particular kind of complex lifeform. (This would be similar to teams in an online shooter or factions in a MMORPG.) In this world, cells die all the time, so the gameplay would support players jumping into and out of cells at will, including into complex cells already hosting other players. The "character" of a cell (i.e., its abilities) would be intrinsic to the type of cell the player chooses to inhabit. So the death of an individual cell would be relatively trivial; the player would simply jump to a new cell. Again, though, this severely restricts the opportunity to create a fully-rounded "character."
3. Allow accumulated assets to be transferred to a new character. In this model, characters can be fully developed with both intrinsic assets (names, personalities, skills, story progress) and extrinsic assets (money, equipment), some or most of which can be transferred to a new character if the player's existing character dies. In a complex gameworld, it should be possible to provide some minimally plausible explanation for this: the magical restoration of souls in a fantasy gameworld, cloning or the transfer of minds in a science fiction setting, and so on.
One special note applies to roleplaying games in which "leveling" progress is a special type of intrinsic asset. In an RPG (including an MMORPG) that follows the usual class/level model, players invest considerable time increasing the level of their characters. This investment radically reduces the acceptability of permadeath. So eliminating leveling as an intrinsic asset would tend to reduce the perceived cost of permadeath.
This isn't as crazy as it might sound to people who've only played today's MMORPGs. There have been successful RPGs that offered virtually no leveling-driven character advancement as core gameplay -- the science fiction RPG Traveller might be among the best-known such game. In Traveller you don't spend any in-game time leveling up your character; all of your character's skills are generated before playing.
The cost of losing a level-free character in a game like Traveller is thus considerably less than losing a character in a MMORPG whom you've spent months leveling up. Only gear tends to be lost... and that could be "willed" to a new character.