Perma-death is great. Do not be scared of it. Instead, what really happens is that YOU the player of the game, learn how to be a better player and survive longer.
To quote from John Harris of @play, in this column he is speaking of what really makes a roguelike (and specifically Mystery Dungeon: Shiren the Wanderer on the Nintendo DS):
http://www.gamesetwatch.com/2008/03/play_the_delights_of_mystery_d.php -------------------------------------------------------------------------------------
The first thing you should know about Mystery Dungeon: Shiren the Wanderer, and something that I wish each of the above reviewers had been told before they wrote their pieces, is that it is a game.
That may seem like an obvious statement, but it's not as simple a declaration as it may first appear. While the G in RPG stands for Game, many are not games in the strictest sense: they care more about storytelling than play, and there is no real way to lose. The definition of game has been only recently expanded to cover the kinds of things most CRPGs are. Some still hold that opinion even now: the kinds of person who turn their nose up at RPGs are probably influenced by those old definitions.
In a Final Fantasy or a Dragon Quest, if your party is wiped out it is not a real failure, for you can always return to your last save. So long as the player doesn't do something grossly stupid, like selling all his equipment and wandering the wilds naked, he's not going to fail at the quest. Meanwhile, Shiren the Wanderer is a game in a more fundamental sense, the sense that you can actually lose at it, and probably will many times before you earn your first win. While it is not real-time, it is still much like a classic arcade game, where games nearly always end by losing. As Dwarf Fortress reminds us, losing can be fun.
But it is still a role-playing game. It and other roguelikes arguably have better claim to that title than other CRPGs. There are games that got inspiration from the earliest incarnations of Dungeons & Dragons, but even now roguelike games, with their "no do-overs" policy, their dependence on player preparation, strategy and volition, and their opportunities for creative play more profound than just hitting the X button repeatedly, feels more like a pen-and-paper RPG session than many Western RPGs, and nearly all other Japanese ones.
The word volition up there isn't used casually, and it gets to the core of what makes roguelikes and traditional CRPGs, which both spring from the same ideas and ancestor games, so different from each other. In traditional games, the player is told, pretty much, exactly what to do and where to go. There may be some subquests, but the focus is on the main story, and there's not a lot the player can do to affect the route he will have to take. Roguelikes require that the player, instead, perceive what his needs are himself, take advantage of the opportunities that present themselves, and make his own way through the dungeon. You cannot play a roguelike passively, letting a story wash over you. You must drive yourself forward and accomplish the game.
-------------------------------------------------------------------------------------
Hope this helps, its a great article.
Rix