Let $P_n(x)=\sum_{\sigma\in S_n} \textrm{sgn}(\sigma) x^{\ell(\sigma)}$. We can view $S_n$ inside $S_{n+1}$ (we identify $S_n$ with the set of permutations fixing $n+1$). If $\tau\in S_{n+1}$ fixes $n+1$ then $\tau\in S_n$. Otherwise, $\tau$ can be written uniquely as $\tau=(m\:\:\: n+1)\circ \sigma$ with $\sigma\in S_n$. Then, \begin{align*}P_{n+1}(x)&=\sum_{\tau\in S_{n+1}} \textrm{sgn}(\tau) x^{\ell(\tau)}\\ &=\sum_{\sigma\in S_n} \textrm{sgn}(\sigma) x^{\ell(\sigma)+1}+\sum_{\sigma\in S_{n}} \sum_{m=1}^{n}\textrm{sgn}((m\:\:\: n+1)\circ \sigma) x^{\ell((m\:\:\: n+1)\circ\sigma)}\\ &=\sum_{\sigma\in S_n} \textrm{sgn}(\sigma) x^{\ell(\sigma)+1}+\sum_{\sigma\in S_{n}} \sum_{m=1}^{n}(-1)\textrm{sgn}(\sigma) x^{\ell(\sigma)}\\ &= x\sum_{\sigma\in S_n} \textrm{sgn}(\sigma) x^{\ell(\sigma)}-n\sum_{\sigma\in S_{n}} \textrm{sgn}(\sigma) x^{\ell(\sigma)}\\ &= (x-n)\sum_{\sigma\in S_n} \textrm{sgn}(\sigma) x^{\ell(\sigma)}\\ &=(x-n)P_n(x)\end{align*} Now inductively, $P_{n+1}(x)=\prod_{i=0}^n (x-i)$. Finally, we evaluate $\sum_{\sigma} \textrm{sgn}(\sigma) n^{\ell(\sigma)}=P_n(n)=\prod_{i=0}^{n-1} (n-i)=n!$.

Very nice proof IvanS, though in your place, I would give some more explanation for why every $m\in\left\{1,2,...,n\right\}$ and every $\sigma\in S_n$ satisfy $\ell\left(\left(m\:\:\: n+1\right)\circ\sigma\right) = \ell\left(\sigma\right)$. (It's because when we compose $\sigma$ with the transposition $\left(m\:\:\: n+1\right)$, the new element $n+1$ doesn't form a new cycle but instead "hooks into" one of the cycles of $\sigma$ (namely, the cycle contianing $m$), so the total number of cycles doesn't change.) The problem has been discussed with other proofs given in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=61&t=334033 .

It's easy to see that for a permutation $\sigma$, $\textrm{sgn} \sigma=n-l(\sigma)$ $(\mod$ $2)$. Also, there are $\begin{bmatrix} n\\ k \end{bmatrix}$ permutations $\sigma$ such that $l(\sigma)=k$, so we have to compute $\sum_{k=1}^{n}(-1)^{n-k}\begin{bmatrix} n\\ k \end{bmatrix}n^k$, but we know $\sum_{k=1}^{n}(-1)^{n-k}\begin{bmatrix} n\\ k \end{bmatrix}x^k=x^{\underline{n}}$, so $\sum_{k=1}^{n}(-1)^{n-k}\begin{bmatrix} n\\ k \end{bmatrix}n^k=n!$. P.S: I used the notation of the book Concrete Mathematics.

Let $A$ be the set of all bijections from $\{1, 2, \cdots, n\} \rightarrow \{1, 2, \cdots, n\}.$ Let $B$ be the set of all functions from $\{1, 2, \cdots, n\} \rightarrow \{1, 2, \cdots, n\}.$ We will prove that the answer to the problem is $n!$ by counting in two ways. We will call a pair $(f_1, f_2) \in A \times B$ $\bold{admissible}$ if $$f_2(x) = f_2(f_1(x)),$$for all $x \in \{1, 2, \cdots, n\}.$ In this way, we know that for any cycle $a_1, a_2, \cdots, a_k$ int he cycle decomposition of $f_1$, we have that $f_2(a_1) = f_2(a_2) = \cdots = f_2(a_k)$. Now, we call an admissible pair $(f_1, f_2)$ $\bold{good}$ if $\textrm{sgn}(f_1)$ is $1$, and $\bold{bad}$ if it is $-1$. Then, we will count the number of good pairs minus the number of bad pairs in two ways. Firstly, it is immediate that this is the sum in the problem. Now, we will count it by fixing $f_2$. Note that when $f_2 \in A$, then there there is only one good pair involving $f_2$ and no bad pairs (namely, the pair $(I, f_2)$ where $I$ is the identity permutation). This is because the condition implies that each cycle must have only one element in it (since $f_2$ is injective), i.e. it is the identity permutation. However, when $f_2 \notin A$, then there must exist some element of $\{1, 2, \cdots, n\}$, say $1 \leq e \leq n$, which appears at least twice in the range of $f_2$. Now, note that for any $k \geq 2$, there are an equal number of even and odd permutations of $k$ objects. Hence, by applying this to the elements which map to $e$ via $f_2$, we see that there are an equal number of bad pairs and good pairs involving $f_2$. Hence, by summing over all $f_2$'s, we see that the quantity is also $n!$. Therefore, the answer is $n!$, as claimed.