Hey guys, thought I would share my deck I beat Heroic Chenvaala with. I was getting hung up on her and decided to fight freeze with freeze.
Pretty straightforward, just outvalue her, keep her minions frozen and you can eventually beat her down with Jaina. Once you get jaina, you can keep summoning lifesteal elementals to trade with her 4/4 minions leaving them at 1 health to hero power again. Make sure to save some frostbolts, flame cannons, fireballs for the 3/4 that prevents her minions from freezing. You can frostbolt + hero power it down etc.
Played her three times with this deck and won 2/3 so it works fairly well.