Arena is probably best bet as long as you are able to average 3+ wins per run. 7+ gets you your gold back to do another run but 3+ is usually getting your gold worth.
To build collection you should focus on a cheap deck (or hero) you want to play and work on crafting the cards for that deck. Dust all trash cards and even cards for classes you have no desire to ever play. For me I dusted Priest/Rogue cards for a while. Crafting Epics/Legendaries is going to be easier than hoping to get them in a pack. Packs are a good "base" for sure, and sometimes you get lucky, but you're going to have to craft a lot of the missing cards, in which case GvG isn't going to hurt you much. You'll simply lose out on the luck of acquiring a good card from the basic set.
Luckily Blizzard has implemented a couple ways to achieve Classic packs for new players, so definitely take advantage of that. Re-shuffle all 40 gold quests and hope to get a Spectate a Friend quest, and the Tavern Brawls pack.
I would recommend Mage, Warlock and Hunter as "beginner" heroes. Each has cheap decks that can take you to Legend. Mage and Warlock would be my preferred as there are many decks you can create. Mage: Mech/Flamewaker/Freeze/Echo, Warlock: Zoo/Demons/Handlock. Hunter has the cheapest competitive deck but can't do much else.
My highest recommendations for new players:
- Seriously consider purchasing Naxx & BRM with money. If you don't then you will be crippling yourself for a while. The gold you spend unlocking them could have gone toward packs/arenas. If you plan to take it slow then fine but it might frustrate you to be missing so many "core" cards.
- Play a cheap mage deck, probably Flamewaker or Mech. Arenas will be giving you GvG cards so mech shouldnt be too expensive. You shouldn't have to craft too many cards at all.
- While playing Mage, work on building a Zoo deck with Warlock. Most cards are neutrals which can be used in other decks.
- Transition your Zoo deck into a Demon deck if you manage to acquire or craft Mal'Ganis. (GvG card, could get lucky).
- Hunter will use a lot of the same neutrals that zoo will use. Problem I have with hunter is it is boring and 1-dimensional, and even a bit frustrating at times. Hunter is meant to churn out as many games as quickly as possible and maintain a >50% win rate. The common misconception is hunter has a good win rate. You can win fast but you can lose just as fast. Hunter teaches bad habits, bad mindset and the deck doesn't transition into anything. Warlock has a nice transition: Zoo > Demon > Handlock.