One way to see this is to work in $S_4$ instead. There $(1\,2\,3)$ and $(1\,3\,2)$ are conjugates, of course, since $(2\,3)^{-1}(1\,2\,3)(2\,3)=(1\,3\,2)$.
If we have a $\tau$ such that $\tau^{-1}(1\,2\,3)\tau=(1\,3\,2)$, it must factor as $\tau=\rho(2\,3)$ for some $\rho$, and we have $$(2\,3)^{-1}\rho^{-1}(1\,2\,3)\rho(2\,3)=(1\,3\,2)=(2\,3)^{-1}(1\,2\,3)(2\,3)$$
Canceling the $(2\,3)$s we find $\rho^{-1}(1\,2\,3)\rho=(1\,2\,3)$, and it's then easy to see that $\rho(1)$ determines $\rho$ and there are only three possibilities, which are all even permutations. So $\tau$ must be odd and so not in $A_4$.
This may or may not be easier to follow than Tobias' suggestion to brute-force the possible $\tau$s directly. Personally I think it's easier to think about possible stabilizers of a cycle than to keep things straight while trying to conjugate one cycle into another.
Consider any listing of the numbers $1, 2,...,2n$ that obey the following two conditions: (1) The even numbers appear in order (not necessarily consecutively), and the last number in the list is $2n$. For example if $n=4$, the following would be a permissible list: $5,1,2,4,3,7,6,8$.
Each such listing corresponds to a permissible permutation of $1, 2,...,2n$, where a cycle ends with an even number. For instance in the example above, the permutation would be $(5,1,2)(4)(3,7,6)(8)$.
And this correspondence is reversible. Given a permissible permutation, we can get such a listing, by just putting the even number in each cycle at the end of the cycle, and then removing the cycle parentheses to get the listing.
Now start with the even numbers in their proper order $2,4,6,...,2n$. Next place $1$. There are $n$ choices for this--$1$ can go before any of the even numbers. Next place $3$. There are $n+1$ choices here ($3$ could go before any number currently in the list, which now includes $1$ and all the evens). Next place $5$ ($n+2$ ways to do this). Etc.
Altogether there are $n\cdot (n+1)\cdot (n+2)\cdot \ldots \cdot (2n-1)$ ways to construct these sequences; and consequently that is the number of admissible permutations as well.
Best Answer
I'm sorry but I'm gonna give you a proof using conjugation since it is just the easiest. Like you I would indeed be interested in seeing a different proof.
Lemma Let $(x_1, x_2, \ldots, x_n)$ be a cycle (so each $x_i$ is an integer between 1 and $N$ for some $N \geq n$), and let $a$ be a permutation in $S_N$. Then the permutation $a(x_1, x_2, \ldots, x_n)a^{-1}$ can also be written as a cycle of length $n$.
proof The easiest way to show that it can be written in this form is by doing it. For this we need a notational convention: I denote by $a(x_i) \in [1, \ldots, N]$ the number to which $x_i$ is sent by permutation $a$. (So I view $a$ as a function from $[1, \ldots, N]$ to itself.)
Now the permutation $a(x_1, \ldots, x_n)a^{-1}$ equals the cycle $(a(x_1), \ldots, a(x_n))$.
To see that just check where both permuations send a given number $z$. If the two answers are the same for every $z$ we know the permuations are equal.
We know that $z$ equals $a(y)$ for some (unique) $y$. We consider two cases: $y$ is one of the $x_i$ or it is not.
In the first case let's see what $a(x_1, \ldots, x_n)a^{-1}$ does do to $z$. First we let $a^{-1}$ act that sends it to $y = z_i$. Then we have the cycle that sends $z_i$ to $z_{i+1}$ (or to $z_1$ if $i = n$). Finally we have $a$ that sends $x_{i+1}$ to $a(x_{i+1})$. So the answer is $a(x_{i+1})$.
On the other hand what does the permuation $(a(x_1), \ldots, a(x_n))$ do with $z$? Well since $z = a(x_i)$ by assumption, this cycle sends it so $a(x_{i+1})$. So the answers are equal as expected.
In other case, when $y$ is not one of the $x_i$ what do both permuations do? $a(x_1, \ldots, x_n)a^{-1}$ acts by first letting $a^{-1}$ send $z$ to $y$. Then $y$ gets sent to itself by the cycle and finally $a$ sends $y$ to $a(y) = z$, so that $z$ is sent to itself. It is clear that the permutation $(a(x_1), \ldots, a(x_n))$ also sends $z$ to itself when $z$ is not one of the $a(z_i)$ so also in this case the two answer coincide. End proof.
Corollary Let $p$ be any permutation, then $p$ and $apa^{-1}$ have the same cycle type.
proof Let $p = c_1 c_2 \cdots c_n$ with each $c_i$ a cycle. We know from the lemma that $ac_ia^{-1}$ is a cycle of the same length as $c_i$ for each $i$. But now we can just write $$a^{-1}pa = a^{-1}c_1(aa^{-1})c_2(aa^{-1})c_3(aa^{-1}) \cdots (aa^{-1})c_na = (a^{-1}c_1a)(a^{-1}c_2a)\cdots (a^{-1}c_na)$$ which is a product of cycles of the same length as the $c_i$ appearing in the cycle decompostion of $p$. End proof.
I love this trick.
Now how does this relate to your question?
$$ba = a^{-1}(ab)a$$
So we can apply the corollary with $p = ab$.