Of course, you can just consider the case when $p$ and $q$ are primes. A good reference for your question is, I think, Schoof's monograph on Catalan's equation. The case $q = 2$ is solved in Ch. II, and it involves some arithmetic in the ring of Gaussian integers (the argument goes back to V.A. Lebesgue). The case $p = 2$ is discussed in Chs III (for $q \ge 5$) and IV (for $q = 3$): This is just a little bit more laborious than the case $q = 2$, but still "elementary". In the appendix, you can also find Euler's original proof for $(p,q) = (2,3)$, which is essentially based on the same descent argument, though in a disguised form, used to prove that the group of rational points on the elliptic curve $x^2-y^3=1$ is finite and has order $6$. Some others of your cases follow at once from Catalan's theorem (Ch. VI), whose proof in the book relies on Runge's method (Ch. V).