Mulligan for Steward of Gondor, Mirror of Galadriel, or Nenya. If none of those cards are in your opening hand, use Thurindir's ability to bring up Gathering Information. Upon completion search your deck for the Mirror and then use it to bring out the Steward. You should have both in play by at least the fourth round. Once this is accomplished, it's time to bring out the Haradrim. If they aren't in your hand already, is the Mirror to find them. Galadriel's card draw will help with this, as well as allowing you to keep your threat low for a few rounds. If you can bring out Silver Harp this will speed things up, and Protector of Lorien will provide needed stats until the Haradrim are in play.
Once the Haradrim are out, its becomes all about buffing their stats and readying them over and over again. You should be able to get at least one Harad ally in your hand every round. Using Silver Harp, you can now ready two Harad characters. Khaliel's Headress will increase the concentration of Harad characters in the deck as the game progresses. Eventually, you should be able to ready at least three Harad characters every round, especially if Prepare for Battle has been completed. With attatchments, they should be able to handle virtually everything you need. At this point there will also be plenty of opportunities to play the support allies as well; you will not have to rely solely on the Haradrim and your heroes.
It's worth noting that Galadriel does not necessarily need her ring, but it can be very helpful to have in your opening hand to complete the side quest. Her main purpose is threat reduction and card draw. It should also be relatively easy to find Unexpected Courage with the Mirror.