Hearthpwn

Ok, so really once you get this card, you can use it to win pretty much every match.  It becomes the key card in your deck.  The first treasure I took was Entrenchment (+2 health to all minions) so my minions were "stickier" than usual.  I also took Potion of Vitality (double your hero's starting health).  I think First Aid (restore 2 health to all friendlys every turn) also would have been a good choice. 

Having lost to Infinite Toki once already, I tried to construct a deck with a an average low mana cost, and especially no creatures over 4 mana.  Infinite Toki can flood the board with cheap creatures in the early rounds.  If she gets a chance to cast mega-windfury on one of them it's usually curtains.  You need some minions of your own in the early going to try to get control of the board.  After that I tried to take cards that would help cycle my deck so I could get to Impetuous Companion.  Once I drew her, I just emptied my hand as quickly as possible, then exchanged my empty hand for my opponents (usually full) hand.  This usually lead to a swift victory.  In Infinite Toki's case, I actually waited until she completed "Open the Waygate" and then swapped the deck to steal her extra turn spell.

IMPORTANT NOTE - It's possible to take multiple copies of Impetuous Companion as a treasure.  If both copies end up in your hand at the same time, it could set up a situation where you cast the first Companion to swap your opponents hand, and then your opponent casts the second Companion the next turn to swap back, likely nullifying most of the advantage you gained.  For this reason, it's probably better to operate with a single copy.

I just used this card with Toki for the first time in Monster Hunt.  It is Berzerk!  Way OP and no chance it will ever be released in Constructed.