This is the deck I used to beat Under the Ash Mountains several times solo. I found that a Forth, The Three Hunters! deck made the most sense because it is able to generate a lot of willpower with relatively few characters making the Burning Reek treachery less painful. The built-in ability to heal also allowed you to really work around the treachery writhing shadows. Finally, most of the attachments are pretty cheap so you generally won't be adding a lot of threat from effects like Nameless Beast or Ransacked Supplies.
Mulligan
You need to ask yourself how strictly you want to adhere to the setup rules here. My understanding is that all player setup effects happen after quest setup effects. This means that you will have drawn your starting hand and determined whether you will mulligan before the setup effect on Passage Into Mordor takes effect. Your deck should have 44 cards and you will need to mill the top 4 cards. If you reveal The One Ring or Inner Strength I strongly recommend resetting and trying again. When deciding whether to mulligan you want to be sure that you have a good number of restricted attachments that can be spread out. Great early attachments are Silver Circlet, Steed of the North, Celebrían's Stone, Shining Shield and War Axe.
Gameplay
You should be able to generate quite a bit of early willpower with Éowyn, Silver Circlet, Celebrían's Stone or a readying effect like Steed of the North or Unexpected Courage. I generally found that I wanted to really try and complete the side quest as soon as I could to help reduce the number of cards being milled at the end of the round. The side quests can be devastatingly nasty though. Ideally you'd like to see Lost in the Dark as the first side quest revealed. The worst side quest to reveal at the beginning is probably Overwhelming Darkness since you have a lot of cards that you will be playing in the first two rounds. The goal is obviously to flip your contract as quickly as you can. When it comes to resources, you want to save the resources on Elrohir as much as possible because his ability to ready after exhausting to defend will be critical to engaging enemies and keeping Torech Gorgor Patrol out of the staging area. Unless you manage to get Herugrim out on Eowyn, you will mostly likely struggle to take out some of the patrols, so your first copy of Unexpected Courage probably needs to go on Elrohir. The second copy can go on either Eowyn or Elladan depending on what attachments for Eowyn you have out. Once you are set up, you can ignore the sidequests, keep the staging area clear, and quest hard. I was often able to complete a main quest card in two or three rounds once the patrols were out of the way. This quest is very much a race, so once you have control you want to quest hard and have A Test of Will on standby to prevent a nasty treachery.