I play two-handed, and I'm aiming at building a pair of decks capable of handling every single quest in the game, including nightmares... and without losing, ever. That means I'm not just aiming at having 'correct' winning ratios, but even further, 100% victory ratio (or at last as close as I can get to that). No sideboard (I really want to avoid the mess of swapping in-and-out cards for different quests). My decks should be prepared to handle even the hardest nightmare quests, like Escape from Dol-Guldur, Return to Mirkwood, Shadow and Flame, HoN cycle, To Catch an Orc, Deadman's Dike, Battle of Carn-Dum, Battle of Five Armies, etc etc etc

Currently, my decks are:

Denethor-Elrond-Gandalf

Main Deck

Hero (3)
Denethor (Flight of the Stormcaller)
Elrond (Shadow and Flame)
Gandalf (The Road Darkens)

Ally (21)
1x Beorn (Core Set)
1x Bilbo Baggins (The Road Darkens)
3x Envoy of Pelargir (Heirs of Númenor)
2x Erebor Hammersmith (Core Set)
1x Faramir (Core Set)
2x Firyal (The Mûmakil)
1x Gildor Inglorion (The Hills of Emyn Muil)
1x Henamarth Riversong (Core Set)
1x Legolas (The Treason of Saruman)
2x Master of the Forge (Shadow and Flame)
1x Quickbeam (The Treason of Saruman)
1x Treebeard (The Antlered Crown)
3x Warden of Healing (The Long Dark)
1x Yazan (The Mûmakil)

Attachment (23)
1x A Burning Brand (Conflict at the Carrock)
1x Armored Destrier (Temple of the Deceived)
3x Dúnedain Warning (Conflict at the Carrock)
3x Expert Treasure-hunter (On the Doorstep)
2x Favor of the Valar (The Battle of Carn Dûm)
1x Gandalf's Staff (The Road Darkens)
1x Magic Ring (The Crossings of Poros)
1x Shadowfax (The Treason of Saruman)
3x Steward of Gondor (Core Set)
1x Thror's Map (Over Hill and Under Hill)
2x Unexpected Courage (Core Set)
3x Vilya (Shadow and Flame)
1x Wizard Pipe (The Road Darkens)

Event (5)
3x Daeron's Runes (Foundations of Stone)
2x Word of Command (The Long Dark)

Player Side Quest (1)
1x Gather Information (The Lost Realm)

and...

Caldara 2.0

Arwen-Caldara-Círdan

Hero (3)
Arwen Undómiel (The Dread Realm)
Caldara (The Blood of Gondor)
Círdan the Shipwright (The Grey Havens)

Ally (27)
1x Bofur (The Redhorn Gate)
1x Elfhelm (The Dead Marshes)
3x Elven Jeweler (Escape from Mount Gram)
3x Glorfindel (Flight of the Stormcaller)
2x Imladris Stargazer (Foundations of Stone)
3x Jubayr (The Mûmakil)
3x Northern Tracker (Core Set)
3x Pelargir Shipwright (Assault on Osgiliath)
3x Prince Imrahil (The Flame of the West)
3x Rhovanion Outrider (Temple of the Deceived)
2x Zigil Miner (Khazad-dûm)

Attachment (7)
3x Light of Valinor (Foundations of Stone)
3x Narya (The Grey Havens)
1x Necklace of Girion (The Wilds of Rhovanion)

Event (15)
3x A Test of Will (Core Set)
3x A Very Good Tale (Over Hill and Under Hill)
3x Dwarven Tomb (Core Set)
3x Elven-light (The Dread Realm)
1x The Galadhrim's Greeting (Core Set)
2x Will of the West (Core Set)

Player Side Quest (1)
1x Gather Information (The Lost Realm)

Any help would be appreciated, either suggested cards, or changing heroes, or even small changes like amount of certain cards.

*Reserved for later*

Wow. No words.

Well, three obviously, but that’s not the point.

Quite an interesting challenge :). I once get the same project and ending playing those two deck (or close, vilya deck get updated since): http://ringsdb.com/decklist/view/4287 and http://ringsdb.com/deck/view/43448

The fight deck wasn't interesting to play but the both where working very well together. I probably won't be playing them the same way now (want to have more allies in play in my other deck) but it was closest I get to your project since they were no quests that we especially fear (we do lost on a regular basis against escape from dol guldur nightmare and battle at the five armies NM). One of the deck was able to really handle the start of the game, usually the most problematic part of the game, with good heroes that block and kill enemies. having 2 deck with a good mechanic but who need times to be settled is may be not the best thing to do to achieve your purpose.

I would say that doomed cards are essential in your path to the victory. You need to play many things in the first turn to face the brutal set up of many scenarios. Legacy of numenor allow almost a free turn for a reasonable cost and it is crucial. Deep knowledge is also quite good. In exchange a double back is really helpful in a lot of situations. More galadhrims geetings seem adequate too.

I think about a card by card analysis and will try to get back to this later :).