Yeah, aside from the swap trick, there's very little to the Fisher-Yates-Knuth shuffle. It's just following the standard recursive recipe for generating permutations: to generate all permutations on n distinct elements, try every element in the first place concatenated with every permutation of the n-1 remaining elements.
You can implement this directly with hash sets in O(n) time, assuming you're willing to treat hash set insertion and deletion as O(1) operations:
# O(n) time
def shuffle(elems):
elems = set(elems) # O(n) time
xs = []
while elems:
x = choose(elems) # O(1) time (expected)
xs.append(x)
elems.remove(x) # O(1) time
return xs
This whole approach is obvious when you stop thinking of the problem as shuffling an array in place and start thinking of it as randomly generating a permutation of elements drawn from a set. In the final analysis, the optimized in-place implementation of the algorithm with the swap trick does provide in-place shuffling; the way the two halves of the array are used to contain respectively the partial result and an auxiliary set of remaining elements is very much like heap sort.
Not coincidentally, if you interpret the algorithm as I wrote it above monadically, then it can be used to generate either a random permutation or all permutations, depending on whether choose() is interpreted in the probability monad or the list (non-determinism) monad. This shows conclusively that the shuffling algorithm is really just the standard combinatorial generation algorithm for permutations adapted to random sampling. If so, you'd also expect the swap trick to be useful for generating all permutations in place. Well, of course:
void perms(int *xs, int n, int i)
{
if (i == n) {
for (int j = 0; j < n; j++)
printf("%d ", xs[j]);
puts("");
return;
}
for (int j = i; j < n; j++) {
swap(xs + i, xs + j);
perms(xs, n, i + 1);
swap(xs + i, xs + j);
}
}