Fortunately, there are people out there who have opened several hundred packs and documented the results. Overall, it looks something like this:
* Legendaries average 1 every 20 packs.
* Epics average 1 every 5 packs.
* Rares average 1 per pack. (While each pack is guaranteed to have at least 1 Rare+ card, sometimes you get multiple Rares and sometimes you get no Rares because your guaranteed Rare+ became Epic or Legendary.)
* Commons make up the rest.
* 10% of Rare+ cards become Golden.
* 2% of Common cards become Golden.
We're going to assume these numbers are exact. Most likely there is some sort of Diablo-esque drop table in the actual implementation, but without access to an official source, this is the best we can do.
2. Law of large numbers is our friend.
With 33 legendaries in the game and 20 packs per legendary, a first-order estimate is that we'll need to open 20*33log(33) packs, or about 2300. (Why the log? Read about the Coupon Collector Problem!) The actual number, which is what we're trying to compute precisely, will be lower due to the dust mechanic.
The point is that there are a lot of packs we're opening here, and given that packs are independent and identically distributed (another assumption, but an uncontroversial one), the relative standard deviation over 2300 samples is something like 2%. This means that the error in assuming the number of cards of each rarity we get is deterministically equal to its mean is of the order of magnitude of 2%. Since our only available data are the mean frequencies, we have no choice but to make mean-only computations anyway, but this justifies that the error will likely be quite small.
3. Legendaries will be the last to be completed.
I don't think anyone will find this surprising, but it's worth doing the computation. We already saw that the Legendaries will take around 2300 card packs to collect, minus whatever the dust mechanic gets us. The 37 Epics will take around 2*5*37log(37)=1336 packs, the 81 Rares will take around 2*1*81log(81)=712 packs, and the 94 commons will take around 2*(1/4)*94log(94)=214 packs.
Coupon collecting time is known to concentrate around its mean, so we are almost certain that the last cards to be added to our collection will be Legendaries. What this means is we can pretend the other cards only matter as far as their dust value is concerned!
4. Non-Legendary dust.
Ignoring Legendaries, each deck averages roughly (0.18*100+0.02*400) + (0.9*20+0.1*100) + (3.7*5+0.1*50) = 77.5 dust. The opportunity dust value of the cards we aren't disenchanting because we want to keep them is 37*2*100 + 81*2*20 + 94*2*5 = 11580 dust. Thus, the amount of dust we will have from disenchanting non-Legendaries after n packs is around 77.5n - 11580.
5. Finally, the Legendaries.
We want to work out how many Legendaries we need to pick up in order to have 33 unique Legendaries. Again by Coupon Collector, the number of Legendaries we need to expect k unique ones (for k close to neither 0 nor n) is 33log(33/(33-k)), which means that after n Legendaries, we expect to have 33(1-exp(-n/33)) unique ones. This means there are n-33(1-exp(-n/33)) Legendaries worth of dust.
Adding in the extra dust from the n/10 Golden Legendaries and the rest of the 20n card packs, the amount of dust we have is
400*(n-33(1-exp(-n/33))) + (1600-400)*n/10 + 77.5*20n-11580. We want to set this quantity equal to 1600*(33exp(-n/33)+2), which is the number of Legendaries we need to craft, including Gelbin Mekkatorque and Elite Tauren Chieftain (you can craft them but can't pop them, right?). This comes out to:
2070n - 27980 - 39600exp(-n/33) = 0
A quick numerical solve gives n = 23.
6. A small adjustment.
Oops! 23 Legendaries corresponds to 460 packs, which invalidates our assumption that we'll have gotten all the Epics and Rares without crafting. However, we're only a little bit off. At 460 packs, we expect (again by Coupon Collector; working omitted from now on) to have 34 out of the 37 Epics, 29 of which we have a pair, and all 81 Rares, 80 of which we have a pair. This means we need 11*400+1*100 = 4500 dust to craft the rest, which at 103.5 dust per pack (including dust from Legendaries) will take another 44 packs.
Of course, we should subtract a little bit because we're likely to get lucky and hit one or two missing cards without needing to craft. Let's round things off and subtract 4 packs, giving us an even 500 packs.
7. Error estimates.
We said we'd be working with means only, but that doesn't mean we can't give a quick error estimate. The main variance comes from our Legendaries: how many we get, and how many duplicates we get. Ignoring the freak occasions we get multiple Legendaries in one pack, the number of Legendaries in each pack are independent 0-1 random variables with very low probability, so the variance of their sum is about the same as the mean. This gives a standard deviation of about sqrt(500) = 22 packs. If this seems low to you, don't forget: at this point, almost all of the value is coming from dust, not cards.
Thus, somewhere around 450-550 packs should do the trick.
* You need around 550 packs to reliably get a full collection. This will cost you a little under $700 in cash, or around 500-1000 hours depending on your playstyle.
* The arcane dust mechanic has a huge effect, reducing the average number of packs required from 2300 to 500.
* Typically, you will pick up half your Legendaries and craft the other half. Almost all of the other cards will come naturally.
* The accumulation of dust is actually quite close to being split 1/4 each between Legendaries, Epics, Rares and Commons. All those little bits of 5 dust and the occasional 50 really add up.
* With numbers of this size, the variance is relatively small, especially since half your Legendaries will come from dust. Assuming you don't use dust inefficiently, you are very likely to hit a full collection somewhere between 450 and 550 card packs.
* Although, it does depend heavily on our assumptions about drop rates...