It's not as uphill battle as you might think. I have a lot of friends that started late, struggled to go through a low ranks for some time - like a month, month a half, and than just getting there to rank 15, than 10, than 5. You can see examples on this forum too.
Easiest and best way is to find a cheap deck that is good - like Aggro Shaman, Zoo, Mech Mage - something along those lines - and stick with that. Play it, learn it inside-out and you'll do great.
Also, you can watch Trump Teachings on youtube, also Trump F2P runs where he makes a new F2P account and gets it to legend - I think he's last run only took 2 months or so - he let cards dictate what he plays, and it was priest.