Priests are a fairly simple class to use. Just hit the boss at a high enough level with enough health potions.
Priests can (and should) hit high level undead early. Between the extra undead-specific damage and the priest's high health, they can easily survive against undead enemies a level or two above them.
Race And Deity Choices
Halfling is perhaps the most obvious choice of race for a priest, allowing for, at a minimum, 10 health potions in a standard game. This is especially useful for challenge dungeons. For halflings, carrying glyphs or leaving them on the ground until you actually need to convert them is a good idea. Humans are another solid choice, being able to use the attack bonus to take advantage of higher max health. Dwarves would potentially have another 6/level max health at their disposal, making it easier to take on slightly tougher enemies early on. In both cases, hitting high level undead as early as possible without wasting potions is a good idea.
Since you get the best mileage out of fighting undead enemies, picking Dracul as a priest is a great way to make your life harder and shorter (and he doesn't accept priests anyway). Glowing Guardian also loses out since the chief benefit is from his healing, which you can already do effectively with your potions. Aside from that, though, priests can make use of basically any other deity's powers.
Go halfling to make both bosses much easier, hit gorgons early on. Especially easy to take down Medusa early if you have a decent attack, as your potions will always make you non-petrifiable.
Double physical damage against undead makes this very easy. Finding ways (Glowing Guardian, Taurog, going human, fine sword etc.) of increasing your damage will make this even easier.
Halfling makes everything easier, as usual, especially absorbing Aequitas' high damage. Fireballing high-level imps out of the way helps things along.
You should be durable, and this means either Dwarf or Halfling. Actually, Halfling is, as usual, more powerful.
Level up quickly by fireballing Animated Armour. If you find the APHEELSIK, then smack, fireball and poison Super Meat Man to death, while exploring tiles in search for Iron Man. You are going to have map uncovered, by the time you finish the butchery, so you will have enough potions and powerups to finish Iron Man too. Do not forget about the level-up trick - actually killing Super Meat Man will give you a good kick to next level.
If you fail to find APHEELSIK, then consider this tactic: at high levels with a little powerup like Dwarven Gauntlets or Plate Mail you will be able to withstand one hit from Iron Man and one hit from Super Meat Man without healing. Strike them both, since after drinking health potion you will be able to strike again. If you are a halfling you will finish Iron Man in 6-7 potions and the rest will help you to smack down the Meaty. Taurog, Jehora and any weapon powerup will play nice.