Roguelikes and roguelike-likes (Spelunky, The Binding of Isaac) tend to share a number of game design elements:
I can understand why starting with permadeath as a premise would lead you to the other ideas: if you're going to be starting over a lot, you'll want variety in your experiences. But why do the first two elements imply a permadeath approach?
From a pragmatic standpoint..
If someone isn't going to be playing your game over and over again, but instead is going to play through once from start to end using checkpoints or free saves (like in most non-roguelikes), then why would you spend your time on implementing procedural generation for your world, instead of just making a single, static, well-balanced progression of maps?
I think the important concept is that if you're going to invest in procedural generation of your levels, then to get value from the procedurally generated levels, you really have to make someone want to play your game -- from the start of the procedurally generated content -- several times. And preferably, lots of times. Permadeath is one effective way to do that.
The Diablo games, on the other hand, accomplish this same goal by letting you start over again with your levelled-up character at a higher difficulty level, after winning. Their difficulty level scales up so that a single "playthrough" can wrap around the game several times, and so experiencing several variations of each level.
Lots of other games embed a repeatably-visitable procedurally built dungeon into a static, traditionally-created framing game (commonly an RPG of some sort. e.g.: Persona, Dark Cloud, Mystery Dungeon, etc). In this type of system, separate visits to a single dungeon generate different dungeon layouts. This also allows a single "playthrough" to wrap through your procedurally generated content several times.
These are both different game mechanics which achieve a similar net effect to permadeath, in terms of justifying the use of procedurally generated content.
Of course, permadeath makes more use of (and puts more pressure on) the procedural generation of your world than other approaches, since the user can easily wind up seeing variations on level 1 over and over and over again in close succession, if he dies and has to restart a lot. If your procedural generation of level 1 doesn't make the level unique enough to keep a player from getting bored with it after five or ten successive restarts, then maybe you should think about using a different mechanism to entice players into starting a new playthrough.
But why do the first two elements imply a permadeath approach?
I don't think character growth or procedural world generation imply permanent death at all. In fact, there isn't a necessarily mechanical connection between any of those three elements (as evidenced by the fact that combinations of a subset of those elements in games exist).
I simply think that roguelikes have a tendency to include those design components because the original Rogue employed them, as did its early offshoots, and thus it became a trend.
In other words, to answer the title of your question as well, permadeath is "essential" only in that it is traditional.
Permadeath gives character building and world exploring decisions weight.
Permadeath makes it harder to abuse the random number generator (grinding).
These things help stop a roguelike feeling flat. Procedural content is rarely aesthetically pleasing, so roguelikes rely on creating interesting mechanical space; typically through risk/reward dynamics. The ability to take back mistakes softens the risk, and makes the mechanical space less exciting.
One of the major game-mechanical aspects of classic roguelikes such as Nethack is that you don't know what the potions, scrolls, and wands that you collect do until you try them (and sometimes not even then). There's therefore a big element of risk - is this potion poison or healing? Is this scroll Enchant Armor or Destroy Armor? Any "undo" or save-restore backtrack ability undermines this, and you'd lose the desperate "I'm gonna die on the next turn but maybe this last scroll will turn out to be Teleportation" moments that make roguelikes extra-exciting.
I like to think of "permadeath" as just part of the genre.
For instance, could you make a first-person shooter with no guns? Sure! You could replace them with swords, etc. But would people see it as a FPS? Probably not.
Roguelikes, by tradition (and arguably, by definition), include permadeath because that's the way the genre was defined.
I think one of the core concepts of roguelike games is the inherent humor of your history of failure.
For some people it is fun to look back and realize which decisions ultimately lead to their doom, "decisions" you often were not really at liberty to make at all. All this in a world that constantly tries to kill you with almost no knowledge about it. Also, a lot of these games are incredibly and deliberately unfair: There might be a high-leveled Lich behind the next door, even on the top level. That way every decision has unforeseeable consequences.
So in the end these games create a tragic hero whose doom is pretty much predetermined and the only question is: How? This inability to escape the forces that be might also be a sarcastic comment on life itself - and that's the humor in it.
But why do the first two elements imply a permadeath approach?
They don't.
You can have perfectly functional gameplay without permadeath, while still allowing ability-based character progression and procedurally-generated worlds. Terraria's a good example of this.
What you've done is broken down the Roguealike "genre" too far. You've stripped out important elements.
Consider this. If you want the player to see your procedural engine, to really make use of it, does permanent death help. Yes... provisionally. That provision being that the player die. A lot. Permadeath in a game where death is not common doesn't aid seeing more procedural worlds at all.
Therefore, in order for "Procedurally generated worlds" and "Permadeath" to synergize, you need a third element: killing the player a lot. Roguealikes tend to employ methods to kill players that would generally be seen as brutally unfair ("here's a potion, but I'm not going to tell you what it does. It might kill you or save you. Drink it to find out.").
So the reason why you don't see the connection between the elements is because you're missing elements essential to the genre. You need to combine "permadeath" with "dies a lot" before it starts to connect with "procedural world generation".
It isn't "essential" and IMO is here only as tradition. Sizable amount of players circumvent it with backing up saves.
There are solid design reasons why this is a winning combination of factors, but I think they're missing the point for your question.
These three factors are combined in a rogue-like because that's what makes it a rogue-like
That may seem tautological at first, but it's actually definitional. A rogue-like is a game that combines those three elements. A game without those three elements will be misleading potential players about its nature if it claims to be a rogue-like. It would be like billing your game as an FPS when, in fact, it only supports a third-person view; which won't make it a bad game but it does make it a misleading description.
You could then ask why "rogue-like" means these three things but we're then into a world of historical accident and etymology which ultimately doesn't matter for your question. However it got to mean that, that's what it means.
Permadeath and procedural generation are two sides of the same coin. Without each other, both are meaningless.
Without permadeath, players will never see your procedural content. You may as well make static maps as in other RPGs, as many players may never even realize that the game was random to begin with. The most common alternative employed by modern rogue-ish games (such as Diablo and Starbound) is for the same character to explore multiple dungeons, essentially achieving the same effect under a different name.
Without procedural generation, permadeath is pointless - there's no reason to force players to restart if they'll see the same thing every time. As you said, without variety there's no reason to keep playing. This ties into your observation of character growth through varied powers, adding variety to not just situation but to overall strategy.
The presence of these two features can also (partially) explain some other features common to traditional roguelikes that could otherwise seem quite unreasonable.
Traditional roguelikes are strategy/turn-based rather than action-based so as to give the player some sense of control over permadeath and procedural content (or real control in the case of skilled players). You'll notice that realtime roguelikes are still slow-paced (ie. ToeJam & Earl), which leads to a similar playing experience.
Traditional roguelikes are extremely difficult because otherwise permadeath would never occur, leading to the "never seeing procedural content" issue. This and the above amplify each other, as increased difficulty makes control more important, while the slower-paced genre makes difficulty more justified.
Traditional roguelikes generally don't have stories because it would lead to the "no varied content" issue. The few exceptions rely on story structures very different from most RPGs, such as Dwarf Fortress with half-procedural and half-user-generated stories, or Cogmind with its story mostly contained within randomly-found and optionally-read lore entries.
