Prove that every set with more than one element has a permutation without fixed points

Order the bijective functions $f\colon A\to A$ such that $f\le g$ if all fixed points of $g$ are fixed points of $f$ and $f$ and $g$ agree on all elements that aren't fixed points of $f$. Given a chain with respect to this partial order, an upper bound is given by the function that has fixed points where all elements of the chain have fixed points and maps every other element to the unique element that some elements of the chain map it to. Thus by Zorn's lemma there is a maximal element with respect to this partial order. If this maximal element had at least two fixed points, we could map those two fixed points to each other to create a greater element. Thus the maximal element $f$ has at most one fixed point $x$, and if so we can choose some other element $a$ and define $g$ to coincide with $f$ except $g(a)=x$ and $g(x)=f(a)$. Then $g$ has no fixed points.

If $A$ is infinite it is equipotent to $A\times\mathbb F_2$, and $(a,x)\mapsto(a,1+x)$ does the job.

Here is another proof for fun. It can easily be shown that the axiom of choice is equivalent to the statement that every nonempty set admits a group structure. Give $A$ a group structure, and let $f:A \to A$ be left multiplication by a non-identity element of $A$.