The most obvious way is to gain strength. Various ways to do that are listed on the Nethack wiki.
In addition to that having a blessed (or even uncursed) Bag of Holding helps greatly, so doing Sokoban early may help (though of course there's only a 50:50 chance that you'll get a Bag of Holding there).
Other than that the best way to not be overburdened, is to stash the things that you don't need right now somewhere and come back to it later when you can carry more.
If you get an early wish it's also a good idea to wish for dragon scale mail. Not only are they the best armour in the game, they're also the the lightest. (You could of course also wish for a Bag of Holding, but if you only have one wish, I'd rather go with the dragon scale mail since that's also useful beyond losing weight).
For knights it is also helpful to know that you'll have maximum carrying capacity when riding.
The only ways to protect against the death effect directly are magic resistance and reflection. In fact, because of other dangers in Fort Ludios, mostly ending in "DRAGON", I really recommend trying to get reflection before advancing. You'll probably survive in the lower levels to try and get that stuff moreso than you'll survive in Fort Ludios.
Failing the possession of such, pretty much the best you can do involves the standard method for assaulting ray attackers, which you acknowledge you're already doing. So I'm just going to write this for those who aren't familiar with it. It involves a position as follows:
...|
..%+
.@.|
Where @ is you, + is the door leading to the big area of Fort Ludios (and it will probably be open), and % is Mount Doom.
The advantage of this position is that enemies who approach can only fight you one at a time, they can only move straight from the doorway, and they cannot blast you with wands from a range. So the only place they can reach you is by stepping in melee.
You have a few different ways to capitalize on this. Here's some (and what you, yourself, are looking for).
Be very fast, or at least fast. With boots of speed, a potion of speed, or a spell of haste self, you gain extrinsic speed to be "very fast", while you can get intrinsic speed of "fast" by zapping yourself with a wand of speed or eating certain corpses. This can let you deal much greater melee damage when they step in before they get a chance to fire off the ray.
If you have a wand and sufficient resistance to its effects, use it! For example, use a wand of sleep if you have sleep resistance, and then just massacre the fellow while the soldier is helpless. sjohnston's answer also covers some other options that you can use to disable the foe for your easy killing.
Have a polearm with enough training (unfortunately, I don't recall how much Valkyries get but I hope they get at least to Skilled). This can let you pound enemies at a knight's move away from yourself, which is where the door is. You do this by applying the polearm. Lances can also be used, but I don't imagine you'll have one. The highest damage polearm, by the way, is the halberd.
If you combine this with being very fast, by the way, it's really effective with a good halberd.
Wear an amulet of life-saving. It's gonna be painful to lose it, but they're meant to be used.
Even with death protection, you want to use this kind of strategy to handle this kind of foe, and any foe with a linear ranged attack. With the wand of death in particular, you can use this strategy to defeat the enemy before he uses up any of the charges, which is a much better result for you.
Best Answer
That does look like a pretty bad situation to find yourself in. Still, if you can just survive long enough, you're bound to sooner or later obtain some solution to your problem, if only via random death drops from monsters you kill. So your problem becomes one of staying alive long enough.
If you happen to have a ring of slow digestion, that will significantly reduce your starvation risk. You should remove any other rings or amulets, at least whenever you're not actively fighting monsters, to avoid ring hunger. Also avoid casting any unnecessary spells, jumping (with the spell or with jumping boots) and fighting monsters that you can't eat and don't have to fight, since all of those activities consume extra nutrition.
Your biggest problem, in terms of finding monsters to kill and eat, is that a lot of them will be generated in the other parts of the level that you don't have access to. NetHack's monster generation algorithm tries to place new monsters where you cannot see them, so to maximize the chance of new monsters ending up in the same part of the level as you, you should either blind yourself or, if you can't do that, wait in the smallest room you can find, with the door closed.
If you happen to know the create monster spell, spam it as much as you can. (Don't wait until you're hungry, since casting it does cost some nutrition.) Make sure not to stand next to any wall that you can't get around, since the created monsters can end up on the other side of the wall. Wands and scrolls of create monster are also helpful, but only have a limited number of uses.
Also note that, if your hunger status ever gets to "Weak" or worse, you can pray to try and get it fixed. If you avoid wasting nutrition on anything unnecessary, the 900 points of nutrition you get from prayer is usually enough (at least assuming that you have't been crowned and haven't killed the Wizard yet) to keep you alive until you can safely pray again, even if you find nothing to eat in the mean time. And if you can kill and eat even a few monsters every once in a while, that "usually" becomes a near certainty.
If you should be lucky enough to run into a brown or a black pudding, make sure to split it and let it heal before killing it. If you're playing NetHack 3.4.3 or earlier, a properly managed pudding farm will give you unlimited death drops (and sacrifices, if you have an altar); this has been nerfed in version 3.6.0, but you can still use puddings as an unlimited food supply.
The wiki page on the foodless conduct might also have some useful tips for surviving without food.
Also, keep your eyes open for any unconventional solutions. For example, reading a cursed scroll of teleportation will levelport you, of course, but so will reading a normal scroll while confused, too. Using a magic whistle next to a wall has a chance of teleporting your pets to the other side, where they might be able to wake up the Master Assassin (although ordinary domestic pets probably won't attack him). A magic lamp or a smoky potion may grant a wish, especially if blessed. Any holy or unholy water should be carefully conserved, since many useful items need to be blessed or cursed to work; if you don't have any, the confused remove curse trick may be worth considering.