This proof uses covering spaces, but I'm posting it at the request of orlandpm (the OP).
Consider the $2$-oriented graph, $G$:
This space is the wedge sum of two circles. Therefore its fundamental group is the free group on two generators $\langle x, y\rangle$.
This space has the following covering space, $\widetilde G$:
Since the map $p_* : \pi_1(\widetilde G) \to \pi_1(G)$ induced by the covering space $p : \widetilde G \to G$ is injective, it follows that the fundamental group of $\widetilde G$ is isomorphic to $\langle x^2, xy, y^2\rangle$.
At the same time, $\widetilde G$ is homotopy equivalent to the wedge sum of three circles. Therefore its fundamental group is the free group on three generators, $F_3$.
We conclude that
$$
\langle x^2, xy, y^2\rangle \cong F_3.
$$
For the theory behind this, check out section $1.3$ of Hatcher's Algebraic Topology book (available freely online). (Images courtesy of the book.)
By definition, ${\circ}\colon G\times G\to G$ is a map with codomain $G$, i.e., it maps everything to some element of $G$.
Since $G$ is finite, then $S=\{x^n : n\in\mathbb Z\}$ is also finite since it's a subset of $G$. Thus some $x^n$ are repeated; otherwise we could set up a bijection between $\mathbb Z$ and $S$ which would prove that $G$ is infinte.
Your proof is basically correct — you're showing that repeatedly applying $\circ$ to things in $G$ keeps you in $G$ — but this is quite obvious.
Best Answer
I answer the question just to remove it from the list of unanswered questions.
Of course, the simplest solution is probably to use Nielsen-Schreier theorem: if $a$ and $b$ commute, then $\langle a,b \rangle$ is an abelian subgroup; but the only abelian free group is $\mathbb{Z}$, so $\langle a,b \rangle$ is cyclic.
Otherwise, the result can be shown thanks to a combinatorial argument from the classical normal form in free groups. The proof is made by induction on $\mathrm{lg}(a)+\mathrm{lg}(b)$, and the argument follows the hint given by Derek Holt; the same proof can be found in Johnson's book, Presentations of Groups. The case where $\mathrm{lg}(a)$ or $\mathrm{lg}(b)$ belongs to $\{0,1\}$ is obvious, so let us suppose that $\mathrm{lg}(a), \mathrm{lg}(b) \geq 2$.
First, we write $a$ and $b$ as reduced words on a free basis $$\left\{ \begin{array}{l} a= x_1 \cdots x_m \\ b= y_1 \cdots y_n \end{array} \right., \ n \leq m.$$
Then, we have the reduced product $$x_1 \cdots x_{m-r} y_{r+1} \cdots y_n =ab =ba = y_1 \cdots y_{n-s} x_{s+1} \cdots x_m.$$
Notice that $$m+n-2r-1= \mathrm{lg}(ab)= \mathrm{lg}(ba)= m+n-2s-1$$ implies $r=s$. Moreover, $0 \leq r \leq n$.
Case 1: $r=0$, there is no cancellation in the product. Then $y_i=x_i$ for $1 \leq i \leq n$ hence
$$ a = \underset{=y_1 \cdots y_n=b}{\underbrace{ \left( x_1 \cdots x_n \right) }} \cdot \underset{:=u}{\underbrace{ \left( x_{n+1} \cdots x_m \right) }} = bu.$$
Notice that $u$ and $b$ commute: $$bu=a=b^{-1}ab= ub.$$ Therefore, the induction hypothesis applies, and it is sufficient to conclude.
Case 2: $r=n$, the number of cancellations is maximal. Then $y_i=x_{m-i+1}^{-1}$ for $1 \leq i \leq n$ hence
$$a^{-1} = \underset{=y_1 \cdots y_n=b}{\underbrace{ \left( x_m^{-1} \cdots x_{m-n+1}^{-1} \right) }} \cdot \underset{:=u}{\underbrace{ \left( x_{m-n+2}^{-1} \cdots x_m^{-1} \right) }} = bu.$$
You conclude that $b$ and $u$ commute and you apply the induction hypothesis.
Case 3: $0 < r <n$. Then $x_1=y_1$, $y_1=x_m^{-1}$, $y_n=x_m$ and $x_1=y_m^{-1}$. Let $z:=x_1$, $a'= x_2 \cdots x_{m-1}$ and $b'= y_2 \cdots y_{n-1}$. Then $a=za'z^{-1}$ and $b=zb'z^{-1}$. Finally, you may apply the induction hypothesis to $a'$ and $b'$, and conclude.