Si quieres que se haga dentro de la misma página, si o si tienes que usar AJAX, pero no es tan complicado, lo que tienes que hacer es:
1. Diseñar una página simple con sólo código php no hay necesidad de HTML ni nada por el estilo, donde hagas la consulta respectiva a la BD y haga las verificaciones de si existe o no. Yo lo que hago es que si encuentra que un correo ya existe imprima con echo un 1 y si no encuentra concidencia imprima un 0.
2. Luego debes llamar a través de AJAX a esa página y leer el resultado que imprima la página php. Mira esta
página, esa es la forma que yo uso y me parece más fácil.
3. Luego tienes que programar la forma como va a ejecutarse esa función de AJAX, yo lo hago con el evento onblur del textbox donde se escribe el correo o el usuario. Revisa
esto en donde te explican como usar el evento onblur.
En resumen sería: el usuario escribe el usuario, pasa al siguiente campo, al cambiar de campo se activa el evento onblur que llama a la función que usa el AJAX, la cual a su vez usa el archivo php para hacer la consulta, toma el valor devuelto por la página php y de acuerdo al resultado hace una u otra acción.
No es tan complicado. Si no fuera tan largo tu código te diría dónde ir colocando las cosas, pero si lees lo que te puse vas a ver que es bastante fácil. Si te atoras en algún punto escribes y miramos que hacemos.