Haha, hey, don't feel too bad about being unable to beat him at level 41. I just beat him today after many failed attempts and I'm at level 53. Pretty sad, huh?
What I did was put in about six or seven heal cards at the end of my deck, and then the rest of my cards were just melee attacks. I think I had only a couple nines, a few eights, but most were sevens and sixes. I don't think I had anything below five. And I didn't have any zeros.
As for atttacking, pay more attention to his cards than you normally would any other battle. Most of them are zeros, so easy to break, and then keep moving when he brings out a higher number and shuffle through your deck at the same time to find something that is equal or better. That should leave him open for a few good swings, then get out of there before he has time to recover. Don't bother rushing at him. His shield will block you every time. Took me a while to figure that out...
To avoid his freeze attack, lock on so you can see what he's doing. Otherwise, you'll just be making blind guesses when to roll, as the others have been saying. To avoid the ice spikes, I just jumped and glided until they disappeared, or you could just run away. That's easier. To avoid the shooting ice thing, just time your roll to avoid it.
That's all I did... I hope I helped a little. Or maybe you've already beaten him. *shrug* Either way, good luck.