Is there any way to avoid using Axiom of Choice in proving this theorem?

Of course the axiom of choice is not needed.

First of all, $\Bbb Q$ is countable. Just enumerate it, and choose the least element in the enumeration from each interval.

Secondly, you're asking if $X$, a subset of $\Bbb Q$ is infinite, since we already know that $\Bbb Q$ is countably infinite. That is all. And since $\Bbb Q$ is dense, the axiom of choice is not needed at all.

I think your proof is correct. You can certainly avoid choice, though. Use the lemma twice to get two distinct rationals $q,r$ in $(a,b)$. Now let $q_0=q$, $q_i=\frac12(q_{i-1}+r)$ for $i\geq 1$. We have $(q_i)_{i\geq 0}$ is an infinite sequence of distinct rationals in $(a,b)$.