Every group is a set (together with a binary operation on the set). Every automorphism of a group $G$ is a bijective function from the underlying set of $G$ to itself (which in addition respects the operation of $G$). So every automorphism of a group $G$ can be viewed as a subgroup of the group of all permutations on the underlying set of $G$; in fact, since an automorphism must send the identity of $G$ to itself, you can even view every automorphism of $G$ as a permutation of the set $G-\{e\}$.
Here you are getting a bit confused because you are viewing your group $G$ as a subgroup of $S_4$ (nothing wrong with that), and then you are trying to understand $\mathrm{Aut}(G)$ (which can be viewed as a subgroup of $S_{G-{e}} \cong S_3$) as acting on the set $\{1,2,3,4\}$ as well. While some automorphisms can be defined in terms of an action on $\{1,2,3,4\}$, not every automorphism can.
If you view $G$ as the set $\{\mathrm{id}, (1\;2), (3\;4), (1\;2)(3\;4)\}$, then letting
$$\begin{align*}
x &= (1\;2),\\
y &= (3\;4),\\
z &= (1\;2)(3\;4)\\
e &= \mathrm{id}
\end{align*}$$
then the automorphisms of $G$ will always map $e$ to itself, and so you can view the automorphisms as being elements of $S_{\{x,y,z\}}$, the permutation group of $\{x,y,z\}$. The elements of the automorphism group are then (written in 2-line format):
$$\begin{align*}
\mathrm{id}_{\{x,y,z\}} &= \left(\begin{array}{ccc}
x & y & z\\
x & y & z
\end{array}\right)\\
f_1 &= \left(\begin{array}{ccc}
x & y & z\\
y & z & x
\end{array}\right)\\
f_2 &=\left(\begin{array}{ccc}
x & y & z\\
z & x & y
\end{array}\right)\\
f_3 &= \left(\begin{array}{ccc}
x & y & z\\
y & x & z
\end{array}\right)\\
f_4 &= \left(\begin{array}{ccc}
x & y & z\\
z & y & x
\end{array}\right)\\
f_5 &= \left(\begin{array}{ccc}
x & y & z\\
x & z & y
\end{array}\right)
\end{align*}$$
and you can verify that each of them is an automorphism; since every automorphism corresponds to a unique element of $S_{\{x,y,z\}}$, and every element of this group is an automorphism, then this is the automorphism group.
However, you are trying to view your group $G$ as a subgroup of $S_4$. Can the automorphisms of $S_4$ be "induced" by some permutation of $\{1,2,3,4\}$? Equivalently:
If we view the Klein $4$-group $G$ as the subgroup of $S_4$ generated by $(1\;2)$ and $(3\;4)$, is every automorphism of $G$ induced by conjugation by an element of $S_4$?
Well, it doesn't. The reason it doesn't is that $x$, $y$, and $z$ don't all have the same cycle structure: conjugation by elements of $S_4$ (or more precisely, by elements of the normalizer of $G$ in $S_4$) will necessarily map $z$ to itself, because $z$ is the only element with its cycle structure (product of two disjoint transpositions) in $G$. So the only automorphisms that can be viewed as coming from "acting on ${1,2,3,4}$" are the identity and $f_3$
Added: However: it is possible to view the Klein $4$-group as a different subgroup of $S_4$: identify $x\mapsto (1\;2)(3\;4)$; $y\mapsto (1\;3)(2\;4)$, $z\mapsto (1\;4)(2\;3)$. It is not hard to verify that this is a subgroup of order $4$, and since it has three elements of order $2$, it is isomorphic to the Klein $4$-group. Now you can indeed realize every automorphism of $G$ via conjugation by an element of $S_4$ (in several different ways). Here's one way: the automorphism $\mathrm{id}$ can be realized as conjugation by the identity. The automorphism $f_1$ is given by conjugation by $(2\;3\;4)$; $f_2$ is given by conjugation by $(2\;4\;3)$; the automorphism $f_3$ is given by conjugation by $(2\;3)$; $f_4$ is given by conjugation by $(2\;4)$; and $f_5$ is given by conjugation by $(3\;4)$. You can now easily see that the automorphism group is indeed isomorphic to $S_3$, since it corresponds precisely to the subgroup of $S_4$ that fixes $1$ (you can take any of the other four one-point stabilizers as well).
Best Answer
A group in which every non-identity element has order $2$ is abelian: to see this, note that $a^2=1$ for all $a$, implies that $a = a^{-1}$ for all $a$, so that $$ab = (a^{-1})^{-1}(b^{-1})^{-1} = (b^{-1}a^{-1})^{-1} =b^{-1}a^{-1}= ba$$
for all $a$ and $b$. It follows that any group, $G$, in which every non-identity element has order $2$ is a vector space over the field $\Bbb{F}_2$ with $2$ elements, and that its group automorphisms are the invertible linear transformations. Hence, if $G$ is finite of order $n$, then $n = 2^k$ for some $k$ and the automorphism group of $G$ is isomorphic to $\mathrm{GL}_k(\Bbb{F}_2)$. The formula for $|\mathrm{GL}_k(\Bbb{F}_2)|$ given in the first answer to this question about the order of these groups shows that this automorphism group cannot be isomorphic to a symmetric group unless $n \le 4$.