Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state
$$
\frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) . $$
This is the superposition of all sequences where the $i$'th position contains a number between 1 and $n+1-i$. It's easy to generate because it's a tensor product of $n$ registers.
Then, find a reversible classical mapping from these sequences to permutations. One way of doing this is as follows. If there is an $i$ in the $t$'th position, take the $i$'th unused number available for the permutation. For example: suppose we have the sequence 24211. This gets mapped to the permutation as follows:
$$\begin{array}{r|l}
24211 & \ \ \ \emptyset \\
4211 & 2 \\
211 & 25 \\
11 & 253 \\
1 & 2531 \\
\emptyset \ \ \ & 25314
\end{array}
$$
To illustrate, the third element of the permutation is $3$ because at the third step, the available numbers are $1$, $3$, $4$, ($2$ and $5$ are already in use) and the second of these is $3$. You can easily check that each of these steps is a reversible computation, and so implementable in superposition on a quantum computer.