After trying out some various strategies, I found a way to beat the ultra unfair Old Man of the Sea encounter. Since he's completely ridiculous, I had to get down on his level, by dueling him until I got the perfect opening hand. Honestly, your deck doesn't even matter, because your troops are worthless, and within 2 or so turns, he's made you discard your entire hand. The way to win? An opening hand with 2x phenteo's gift with full equipment, and the captains parrot talent.
You cast Phenteo's gift turn 1, which the parrot duplicates, then you tap the parrot and cast the other one. That's 9 terrorantula's infesting his deck on turn 1. Then, pray for a whole lot of luck that he draws one in the first turn or two, which lets you auto kill some of his troops, and sends all of the Phenteo's gifts back to your hand. Then you re-cast them all again, which snowballs rapidly where his deck becomes like 80+ terrorantulas, and he's drawing 1-3 every round, which is wiping out his units and giving you way more units than he can disable with his stupid hero power.
Even with the above and a perfect draw, it can go wrong if he forces you to discard your phenteo's gifts before you can play them, because them he steals them and uses them on you, and your strategy backfires horribly. Reward for beating him is a copy of his card, which seems fun, though kind of slow. Not sure it's worth trying to build a deck around it.