We can solve this one using species which possibly qualifies as a
combinatorial proof.
First, observe that 2-regular graphs are sets of undirected cycles,
which is the species
$$\mathfrak{P}(
\mathfrak{D}_{=3}(\mathcal{Z})
+ \mathfrak{D}_{=4}(\mathcal{Z})
+ \mathfrak{D}_{=5}(\mathcal{Z})
+ \cdots).$$
This gives the generating function
$$G(z) = \exp
\left(\frac{1}{2} \frac{z^3}{3}
+ \frac{1}{2} \frac{z^4}{4}
+ \frac{1}{2} \frac{z^5}{5}
+ \frac{1}{2} \frac{z^6}{6}
+ \cdots\right),$$
which is
$$G(z) =
\exp\left(-\frac{z}{2}-\frac{z^2}{4}\right)
\frac{1}{\sqrt{1-z}}.$$
On the other hand, permutations with no fixed points or
2-cycles are the species
$$\mathfrak{P}(
\mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=4}(\mathcal{Z})
+ \mathfrak{C}_{=5}(\mathcal{Z})
+ \cdots)$$
which gives the generating function
$$C(z) = \exp
\left(\frac{z^3}{3}
+ \frac{z^4}{4}
+ \frac{z^5}{5}
+ \frac{z^6}{6}
+ \cdots\right),$$
which is
$$C(z) =
\exp\left(-\frac{z}{1}-\frac{z^2}{2}\right)
\frac{1}{1-z}.$$
Observe that when we multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!}
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
In the present case we clearly have $A(z) = B(z) = G(z)$ and we need
to prove that their convolution is $C(z).$
Note however that
$$G(z)^2 = \left(\exp\left(-\frac{z}{2}-\frac{z^2}{4}\right)\right)^2
\frac{1}{\sqrt{1-z}^2}$$
which is
$$\exp\left(-\frac{z}{1}-\frac{z^2}{2}\right)
\frac{1}{1-z},$$
i.e. precisely $C(z),$ QED.
Here we have used the fact that the dihedral group acting on $q$
elements contains $2q$ permutations and the cyclic group $q$
permutations.