Alright, so this is dumb. I'm going to lead with that right away, and apologize immediately to the strong contingent of LotR players that are 100% opposed to using the Response on Loyal Hound. Advert your eyes now, because Durin's Dane is going to the discard pile over, and over, and over again.
This is a silly little two player fellowship I made just to see how well I could recur our favorite (unwilling?) pin cushion and rely on them to help out with defense (and archery, thanks to the ruling of them being able to absorb it up to their HP and trigger their response) beyond what Denethor and Thengel could themselves handle. So this is two decks with The Last Alliance, one of Creatures and Rohan and one of Creatures and Gondor. Sadly, there isn't much Creature specific support, with most of it being locked into the Eagle trait and Radagast's Staff not being able to help out in any way. Both decks want to build up a board state with fewer creatures than humans, so that the Hounds can be played for just 1 cost with the contract discount.
The Rohan deck is the more consistent of the two, thanks to Gúthwinë being a good way to bring a pooch back and maybe get lucky with Thengel's response finding another creature in your top 5 cards to replace it. Gamling would also be an effective way to bring back a recently discarded companion.
Gondor is unfortunately a bit less reliable than Rohan at recovering their pets after they run off to distract the enemy (themurdered?). Knight of Belfalas is the best bet, ideally tossed into play for free with Lothiriel so that you can recycle them again. Farmer Maggot's dogs help fish them out of the deck at least, so they can be found and paid for a little more quickly than Rohan can.