Hola:

Si no le das a submit, seguramente no se puede hacer sólo con php. Posiblemente neceistas la ayuda de algo como javascript.

Una opción "bruta" es pasar al formulario, desde php, todos los usuarios existentes con POST o GET. Luego javascript podrá sobre la marcha, según se escribe, comprobar si existe o no el usuario, correo, etc.

Otra opción menos "bruta", pero que no sé si es posible, es que le mismo javascript vaya accediendo a la base de datos para comprobar los usuarios.

Se bueno.

Efectivamente se hace con AJAX. La otra opción sería la "bruta" de Chuidiang. Aunque lo hagas con AJAX debes comprobarlo igualmente en el servidor al enviarlo con el submit por varias razones:

1.- Porque los usuarios pueden no tener activado el Javascript con lo que no te funcionaría la comprobación.

2.- Porque un usuario malintencionado puede entrar a tu aplicación sin pasar por el formulario.

Saludos,
Rodrigo