This a continuation of my first answer. I was trying to edit the previous one but the MathJax processing was freezing my computer. I suppose that answer was getting too long.

@Darij: There has been lots of action on this question since I posted my first answer last night. Although, I must say, there has not been much reading of that answer ... ;) 

In your comments your raised two issues.

**Issue 1:** how does FFT imply part b) of Schur-Weyl duality (the hard part)?

My reply: The proof I gave does in one sweep, with no pause in between, the FFT for $SU(d)$ (and not $U(d)$ as in David's answer) and Schur-Weyl duality.
But I could have written it in two steps. In this case the main protagonist $T$ would be an array with entries
$$
T_{a_1\ldots a_p,i_1\ldots i_q}
$$
corresponding to an invariant of $p$ vectors and $q$ covectors. After 
eliminating the matrix elements of $g^{-1}$ by Cramer's rule, one
has a degree $p+q(d-1)=qd+p-q$ homogeneous polynomial in the entries of $g$
to be hit by a suitable power $r$ of ${\rm det}(\partial g)$.
If $d$ does not divide $p-q$ then $T$ must vanish. Otherwise $r=q+\frac{p-q}{d}$ and at the end of the argument above using the elimination of $\epsilon$'s and $\tau$'s in pairs with the identity "${\rm det}(AB)={\rm det}(A){\rm det}(B)$", the number of $\epsilon$'s is $q$ while the number of
$\tau$'s is $r$.

 1. If $p>q$: then $r>q$ and after pairwise elimination of $q$ $\epsilon$-$\tau$ pairs, one is left with $q$ direct contractions of vectors and covectors mediated by a permutation in $S_q$ (this is the Schur-Weyl or $GL$ invariant part) as well as $(p-q)/d$ surviving $\tau$'s giving what the classics called "klammerfaktors" involving vectors only.
 2. If $p<q$: then $r<q$ and after pairwise elimination of $r$ $\epsilon$-$\tau$ pairs, one is left with $p$ direct contractions of vectors and covectors mediated by a permutation in $S_p$ (this is again the Schur-Weyl or $GL$ invariant part) as well as $(q-p)/d$ surviving $\epsilon$'s giving "Klammerfaktoren" involving covectors only.
 3. What you are interested in is the special case $p=q=n$, or pure Schur-Weyl situation with no "Klammerfaktoren".


**Issue 2:** This does not count because the proof uses analysis, Haar measure etc.

My reply: The Haar measure is just salad dressing, so the structure of the proof becomes natural. There three steps only: 1) average over the group. 2) figure out what averaging means in algebro/combinatorial terms rather than analytic ones 3) do the calculation and contemplate the result. It would have taken me too long to draw pictures in my answer but this is a purely graphical proof. If you want to see these pictures at least in the case $d=2$, $p$ arbitrary and $q=0$ case then see pages 16-17 of <a href="https://arxiv.org/abs/0904.1734">this article</a>. (If you have access to JKTR, the <a href="http://www.worldscientific.com/doi/abs/10.1142/S0218216511009522">published version</a> is a quite bit better).

I could have written my first answer in a purely combinatorial way without mentioning the Haar measure at all but then some elements of the proof would have come totally out the blue. In particular, I would have had to all of a sudden say: it $T$ is invariant then
$$
T=c_n\ ({\rm det}(\partial g))^n\ gT
$$
where $gT$ is the expression obtained after Cramer's rule and the $g$'s are treated as formal variables.
So again I insist, my answer is purely combinatorial.
But I don't know if it may be useful in nonzero characteristic. This may require understanding the arithmetic of the $c_n$'s.

**Additional remark:**
A more natural proof in the spirit of the one I gave would to use the FFT for $U(d)$ slash $GL(d)$ rather than $SU(d)$ slash $SL(d)$.
This would need an explicit formula of averaging as an infinite order differential operator. I remember seeing something like that in a physics paper, but I would have to find that reference. Usually people resort to Weingarten calculus which goes in the orthogonal direction of the character theory of the symmetric group.