Hola que tal.
Mira la verdad es que AJAX es mucho mas sencillo de lo que parece. Es comun que los recientes practicantes de la programación en PHP les de miedo interactuar con otros lenguajes de apoyo, como lo es AJAX, pero éste miedo hay que quitárselo.
(En esencia Solo hay 2 formas de hacer eso que quieres con PHP, una es usando un lenguaje Asincronico y la otra es sin usar alguno)
Solo debes de saber que si te decides a no usar AJAX; deberás recoger los valores del formulario "PAIS" y al hacer submit, mediante una nueva consulta con PHP obtengas las provincias.
Esto sería algo asi como:
Código HTML:
Ver originalIndica tu Pais
| SELECT DE FORMULARIO | | submit | <!-- Boton de formulario -->
.
.
.
.
=> muestro provincias
Con respecto a tu última duda.
Cita: Cómo puedo hacer para mantener el Nombre del País en el Select 1 una vez elegido, y cómo puedo mantener y mostrar el nombre de la provincia
Lo que puedes hacer es recibir por POST el valor del campo Pais he insertarlo dentro del campo despues del submit.
ej.
<option selected="selected">$_POST['pais']</option>
Es todo saludos.