If you are unwilling to spend money, then it is simply time and patience. Time and patience will lead to familiarity and better play and a larger collection.
I'm a F2P player. I started around a year and a half ago (roughly May 2015). I'm caught up on all the adventures, I have a couple of decent meta decks (mostly Shaman in the last season of course), I have very few legendaries.
I don't have much time to play. I don't play everyday. When I do have time, I try to do all 3 quests at once for time efficiency. I do any quests that give me free packs (play on different platforms, etc) I do the tavern brawl every week for the free pack.
I spent the first few months not making it above rank 15. Only in the past half a year or so have I been able to make it above rank 10. If I spent more time playing, I believe I could reasonably hit rank 5 each season.
When I started out there were already two adventures available. I focused on saving up gold to unlock each wing, 700 gold/wing at a time. By the time Karazhan came out, I had enough gold saved up to complete each wing as they came out.
My advice for your situation is this: save your gold for unlocking the adventures, work backwards (start with the most recent ones - Karazhan). Get free packs whenever you can. Eventually, you will open a legendary, that you can dust to craft some budget decks.
Find a budget deck you like and start playing. That 800 dust one you mentioned might be okay. Just play it as often as you can and you will become familiar with the deck and other cards in the format.
If you used to play MTG, you should be able to recognize the same learning curve - MTG has way, way, way more cards than HS, even just in Standard, and you don't need to be familiar with all of them, but if you play often enough you start to recognize the really important ones. Identifying aggro decks should be relatively easy - they come out early with a bunch of creatures and prefer to hit you in the face yes?
But in summary