Here is an indirect solution - a solution that doesn't use any specific primitive root. I think a better solution exists, but I would still like to post it because it gives a different perspective.
The solutions $1$ and $m-1$ are obviously always solutions. So the difficulty is proving there aren't any more.
By the primitive root theorem, the possibilities for $m$ are $m=2$, $m=4$, $m=p^k$, or $m=2p^k$ where $p$ is an odd prime and $k\ge 1$.
For $m=2$ we actually have $1=m-1$, and there is a unique square root of $1$.
For $m=4$ you may check directly that the claim holds, just by calculating.
For $m=p^k$, we prove by induction on $k$. For $k=1$ there are no zero divisors, so $(x-1)(x+1)=0$ implies $x-1=0$ or $x+1=0$. For $k>1$, assuming there are exactly two solutions modulo $p^{k-1}$, we use Hensel's lemma to claim that these lift to exactly two solutions modulo $p^k$.
For $m=2p^k$ we use the Chinese remainder theorem to combine the two solutions modulo $p^k$ with the unique solution modulo $2$ to get two solutions modulo $m$.
Let $m\geq 3$ and $g$ is a primitive root modulo $m$. Then $\mathbb Z^*_m$ can be fully represented by $\{g_0,\dots,g^{\varphi(m)-1}\}$. Hence, any $x\in \mathbb Z^*_m$ can be written as $x=g^k$ for some $0\leq k<\varphi (m)$ and working in $\mathbb Z_m$:
$$x^2=1 \Leftrightarrow (g^k)^2= 1 \Leftrightarrow g^{2k}= 1 \Leftrightarrow \varphi(m) \mid 2k$$
which is only possible for at most two values of $k$, namely $0$ and $\frac{\varphi(m)}{2}$. As $\pm 1$ are always solutions and distinct, those are exactly the two solutions.
The other direction is most likely more difficult, I don't have a proof yet, but you can of course deduce this from Euler's theorem:
If there is no primitive root modulo $m$, then by Euler's theorem $m$ can not be of the form
$$2, 4, p^k, 2p^k$$
where $p$ is an odd prime and $k$ is a positive integer. Check carefully, that this implies that $m$ is either a power of two or can be written as product of two coprime numbers which are both at least $3$. In both cases we find more than two solutions:
- $m=2^k$. Define $x=2^{k-1}-1$. Then $x\not\equiv \pm 1\pmod{2^k}$, but
$$x^2=(2^{k-1}-1)^2=2^k-2\cdot 2^{k-1} +1 \equiv 1\pmod{2^k}$$
- $m=ab, (a,b)=1, a,b\geq 3$: Then $x^2\equiv 1\pmod a$ and $x^2\equiv 1\pmod b$ have both at least two distinct solutions ($\pm 1$) and the Chinese remainder theorem tells that $x^2\equiv 1\pmod{ab}$ has at least four solutions.
Best Answer
$$x^2\equiv x\!\!\!\pmod p\,\overset{\rm def}\Rightarrow\, p\mid \color{#c00}x(\color{#0a0}{x-1})$$
Since $p$ is a prime, Euclid's Lemma $\Rightarrow\,\color{#c00}{p\mid x}\ \ {\bf or}\ \ \color{#0a0}{p\mid x-1}$
$$\ \ \Rightarrow\ \color{#c00}{x\equiv 0}\ \ {\bf or}\ \ \color{#0a0}{x\equiv 1}\!\!\pmod p$$
Clearly both are roots of $\,x^2-x= x(x-1),\,$ hence they are the complete set of roots.
Remark $ $ The final "root checking" step is needed to rule out the possibility of extraneous roots due to the use of unidirectional $(\Rightarrow)$ inferences above. In fact all arrows hold bidirectionally, i.e. they are equivalences $(\!\!\iff\!\!),\,$ so we could eliminate the final checking step by using bidirectional inferences everywhere (see here for more on such).