How to prove from scratch that there exists $q^2\in(n,n+1)$?

As $1<(\frac54 )^2<2<(\frac32 )^2<3$, we may assume wlog. that $n\ge 3$.

With $q=\frac ab$, our task is to find $a,b$ such that $nb^2<a^2<(n+1)b^2$. Pick $b=2n^2$; so we want $4n^5<a^2<4n^5+4n^4$. The set $\{\,k\in\Bbb N\mid k^2>4n^5\,\}$ is a non-empty (contains $3n^3$) subset of $\Bbb N$, hence has a minimal element $a$. Clearly, $a>2n^2>1$. Then $$(a-1)^2=a^2-2a+1>a^2\left(1-\frac 2a\right)>a^2\left(1-\frac 1{n^2}\right) $$ If we assume $a^2\ge 4n^5+4n^4$, this leads to $$ (a-1)^2>4n^5+4n^4-4n^3-4n^2=4n^5+4n^2((n-1)^2-2)>4n^5$$ contradicting minimality of $a$. Hence $a^2<4n^5+4n^4$, as desired.

One idea: It's easy enough to find a $q_0 \in \mathbb{Q}$ that satisfies $q_0^2 > n$. Now use Newton's method to approximate a solution to $q^2 - n = 0$. This gives a recurrence $$ q_{i+1} = q_i - \frac{q_i^2 - n}{2q_i}. $$ It can be shown that $$ q_{i+1}^2 - n = \left(\frac{q_i^2 - n}{2q_i}\right)^2 \le \frac{q_i^2 - n}{4} $$ so that eventually $q_i^2 - n < 1$.

Notice that for $n > 4$

$$ n\sqrt{n + 1} - n \sqrt{n} = \frac{n}{\sqrt{n + 1} + \sqrt{n}}\geq \frac{n}{2\sqrt{n + 1}} > 1$$

so there is an integer $k$ such that

$$n\sqrt{n} \leq k <n \sqrt{n + 1}$$ so

$$n \leq \frac{k^2}{n^2} <n + 1$$ hence $q := \frac{k}{n}$ is a rational number with the property you are looking for.