From Wikipedia I found out about the fact that $S_6$ has outer automorphisms.
So the idea is that first you find a transitive copy of $S_5$ in $S_6$. This I was able to do, I found that for example $\langle (1 2 3 4 5),\ (1 5)(2 3)(4 6)\rangle \cong S_5$ .
This gives you a subgroup of index $6$ in $S_6$, let's call it $H$. And so we can use the left coset action or conjugation on $H$ to construct an automorphism of $S_6$ (for conjugation you have to show $[G : N_G(H)] = 6$ ). Then it turns out that this mapping does not send a transposition to its conjugate (another transposition) but to a product of three disjoint transpositions. This means that it is not an inner automorphism.
Okay, makes sense to me. But I have no idea how one should calculate the coset representatives for $H$ by hand, and how to determine how different elements of $S_6$ act on the cosets? I know it should be enough to determine how $(12)$ and $(123456)$ act on the cosets because $S_6$ is generated by these elements. I was able to brute-force a solution with GAP, but it is not a very satisfying way to do it..