all comes with experience mate, i dont find any class impossible to beat, but i find EVERY class can have that perfect deck or luck of draws that just totally wipes you off the board
Your always gonna have classed in which their hero ability is great for pinging off lowbie minions, so think mage/druid/rogue. Shaman hero ability is also nice if you can combine it with a flametounge totem, dire wolf, shattered sun cleric etc.
I would say my least played hero by far is the warlock and thats only because i always find it counter intuitive to take damage to make progress, but its just a personal thing
Very frustrating, just work through getting the basic decks unlocked for every class then look at something like
http://www.icy-veins.com/hearthstone with a nice guide for making starter decks from the basic cards. You will be suprised that you can do pretty well on the starter decks until you hit the higher ranks and come up against more specialised/novelty decks
For myself last night i logged in to get my 3 wins for the WOW mount. God what worst luck i had in my first arena run. Picked a pally and drafted what i thought was a decent deck, had a sword of justice, 2 or 3 argent protectors, silver moon guardian even a couple of argent squires, and then the blood knight appears in the epic group so im thinking gettin a decent synergy deck here.
I then proceeded to go 0-3 getting some awful card draw and meeting some people with just as lucky decks as me.
After that went for another arena run, picked hunter and has pretty much all the cards i could want, scavenging hyenas, starving buzzards, savannah highmane, gladiators long bow etc
Thought ill try and get a rush deck going and ended the night 3-0 with the hunter deck despite not having a taunt or silence in the deck. Gotta love hearthstone