Let's begin by pointing out something important: this deck doesn't exactly follow the rules. The issue here is that At the End of All Things affects your starting heroes, and Frodo is never one of your starting heroes by the rules. But making a thematic deck that can beat Mount Doom is the goal here, so we're going to count Frodo as one of your starting heroes.
So what does this deck do exactly? Through At the End of All Things, it gives Sam the sphere, meaning that The Tower of Barad-Dur won't raise your threat. In fact, because you don't raise your threat at the end of the resource phase, only encounter card effects or failing questing will raise your threat, and the encounter card Old Water-course will even lower it, allowing the 10s digit of your threat to be 1 the entire game, largely neutralizing many encounter card effects and making Fortitude tests easy to pass.
You really need multiple uses of your heroes, so you need Fast Hitch quickly, and Strider too. Galadriel can help you get a useful attachment, and there are a few ways to pay for cards included in this deck. When you flip At the End of All Things, you have the option to grab whatever will be most helpful, whether that be Fast Hitch or two copies of Friend of Friends, which really shines here.
Because the fortitude tests aren't difficult with your threat being in the teens, the treacheries are not all that bad, which means you don't need to absolutely blitz the first stage, instead clearing out locations so you don't get location locked. The only really bad treachery is Heavy and Tired, which Elrond can help with, either through Sneak Attack or playing him outright. If you get a copy on both heroes and can't draw into condition removal, you're done for, so save Elrond if you can.
The deck as listed was able to take on Mount Doom, although it took a few tries. The sideboard includes cards I would want to work in to try to further optimize it, so go ahead and give it a whirl with your own personal spin on it.