Prove that between any two rational numbers there is a rational whose numerator and denominator are both perfect squares.

The following proof does not assume any knowledge of real numbers and square roots and uses only the properties of rational numbers. The argument below is typical of many analytical arguments and is the essence of definition of real numbers as envisaged first by Dedekind.

Let $x, y$ be two positive rationals with $x<y$. We are supposed to find a rational $a$ such that $x<a^2<y$. The problem is easily handled if $y$ itself is a perfect square. Thus if $y=t^2$ then we can choose $a<t$ such that $$y-a^2=t^2-a^2<y-x$$ ie $$(t-a) (t+a) <y-x$$ and this is easily done if we choose $$t-a<\frac{y-x} {2t}$$

We are thus left with the difficult case when $y$ is not a square. Let's consider the set $$A=\{a\mid a\in\mathbb {Q}, a>0,a^2<y\}$$ Clearly this set is non empty and bounded above. We will prove that there is no greatest member in this set. Suppose on the contrary that there is a greatest member, say $m$, in $A$. Then we have $m^2<y$ but for any rational $n>m$ we have $n^2>y$. Let's further assume $m<n<m+1$ and then we have $$n^2-m^2=(n-m)(n+m)<(n-m)(2m+1)$$ And we have an obvious contradiction if $$0<n-m<\min\left(1,\frac{y-m^2}{2m+1}\right)$$ because then we have $n^2-m^2<y-m^2$ or $n^2<y$.

In a similar manner we can show that the set $$B=\{b\mid b\in\mathbb {Q}, b>0,b^2>y\}$$ is non-empty, bounded below and has no least member. Now we can choose some specific members $a\in A, b\in B$ and an arbitrary positive integer $n$ and consider the sequence of numbers $$x_i=a+i\cdot\frac{b-a} {n} $$ so that $$a=x_0<x_1<x_2<\dots<x_n=b$$ In the above sequence there is a last, say $x_r$, which lies in $A$ and the next one $x_{r+1}\in B$ and we have $x_{r+1}-x_r=1/n$. Since $n$ is arbitrary it follows that give any positive rational number $\epsilon$ we can find members $a\in A, b\in B$ such that $b-a<\epsilon$.

Next we set $\epsilon=y-x>0$ and consider a specific number $k\in B$. Now we can choose $a\in A, b\in B$ with $b-a<\epsilon/(2k)$ and also ensure $b<k$. This implies that $a<b<k$ and thus $a+b<2k$ and $$b^2-a^2=(b+a)(b-a)<2k\cdot\frac{\epsilon}{2k}=\epsilon$$ or $$(b^2-y)+(y-a^2)<\epsilon$$ Each term in parentheses in positive and hence individually less than $\epsilon $. We thus have $$y-a^2<\epsilon=y-x$$ or $x<a^2<y$. Thus we have found a rational number $a$ as desired.

The above proof can be worked out (to aid in understanding) for specific example. Let's say we wish to find a square between $x=1.9$ and $y=2$. We take $a=1\in A, b=2\in B$ and set $n=100$ ($n$ is choosen such that $1/n< (y-x) / 2b$) and consider sequence of numbers $x_i=1+(i/100)$. Clearly $x_{41}=1.41\in A, x_{42}=1.42\in B$ and $1.9<1.41^2<2$.

Let rational $\ x\ z\in\mathbb Q\ $ be such that $\ 0<x<z;\ $ for instance, let $\ x:=\frac{p_1}{q_1}\ $ and $\ z:=\frac{p_2}{q_2},\ $ where the fractions are as in the OP's Question. Let $\ y:=\frac{x+z}2,\ $ so that $\ 0<x<y<z;\ (y\in\mathbb Q).$

The classical (and beautiful) Newton's method provides arbitrarily good rational approximations $\ r_n\ $ of $\ \sqrt y\ $ in the most elementary way, and $\ r_n^2\ $ provides an answer to the OP's Question when the Newton approximation is advanced enough.

The consecutive Newton approximations $\ r_n\ $ of $\ y\ $ converge to $\ y\ $ very fast:

$$ \rho_0:= 1\qquad r_0:=y $$ and $$ \rho_n\ :=\ \frac{\rho_{n-1}+r_{n-1}}2 $$ $$ r_n\ :=\ \frac y{\rho_n} $$

for arbitrary $\ n=1\ 2\ \ldots$.

we see that:

$$ \forall_{n=0}^\infty\quad \rho_n\cdot r_n\ =\ y $$ and, depending on $ y\le 1\ $ or $\ y\ge 1$, we get $$ r_0^2\ \le y\ \le \rho_0^2\qquad\mbox{or} \qquad r_0^2\ \ge y\ \ge \rho_0^2 $$ and $$ \forall_{n\in\mathbb N}\quad r_n^2\ \le\ y\ \le\ \rho_n^2 $$

I'll leave the estimates of the wonderful speed of approximation as a pleasant and most rewarding exercise (perhaps in mathematical induction).

HINT:

Let your rationals be $0< r_1 < r_2$. Consider $0<a < b$ rationals so that $a^2 < r_1$ and $b^2 > r_2$. Now consider a set of intermediate points $x_k=a + \frac{k(b-a)}{N}$, $\ k = 0,1,\ldots, N$, where $N$ is sufficiently large so that $0<f(x_{k+1})-f(x_k)<r_2 - r_1$ for all $k$. It should be easy now.

ADDED: This works in a similary for any other "continuous" function $f$, like a polynomial. The property is "weak intermediate value", that is, if $f(a)\ne f(b)$ then $f([a,b]\cap \mathbb{Q})$ is dense in $[f(a),f(b)]$.

Note that even if we "avoid using the reals" in the proof, we used natural numbers and the fact that $\mathbb{Q}$ is an archimedean ordered field ( a subfield of $\mathbb{R}$ as it is).