A common technique for proving that a diophantine equation does not have a solution is to prove that it does not have a solution mod $m$ for a suitable modulus $m$.
This technique works with $m=11$ for the equation $x^5 - y^2 = 4$ mentioned in this question.
Now, $11$ seems to be the only prime modulus that works. Moreover, the other moduli that work are all multiples of $11$. (I've tested all moduli up to $10^4$.)
(This is probably related to the rational points in the hyperelliptic curve $y^2=x^5-4$, but I don't know anything about this.)
Is it true that $11$ is the only prime modulus that works for that equation?
It is possible to use a geometric argument that goes as follows: every time you want to show that a curve $C$ over a finite field $\mathbb F_p$ has a rational point, what you can do is to show that there exists a place of $\mathbb P^1_{\mathbb F_p}$ of degree $1$ which has a place of degree $1$ of $C$ above it (simply because every projective curve comes with a morphism to $\mathbb P^1$ given by a corresponding embedding of function fields). In order to prove this, one can use a strong version of Chebotarev's theorem for function fields. I learned about it here: http://arxiv.org/abs/1404.6345. According to corollary 1.2, if you choose $\gamma$ to be the identity, so that the sum in the formula basically gives you the number of degree $1$ places of $C$, the lower bound that you get looks like $1/N\cdot (p+1-2g\sqrt{p})$, where $g$ is the genus of your curve $C$. Since that particular hyperelliptic curve has genus $2$, this lower bound is certainly positive for $p>7+4\sqrt{3}$, answering positively your question.
I know I did not fill in the details, since this can be pretty long, it was just to give you an idea of a possible method!