Tienes varias formas de hacer eso. La primera y que en realidad no me gusta es mediante JS, necesitaras cargar toda la info y mandarla de una sola vez para que realice eso. Recuerda que PHP se ejecuta solo en el servidor y una vez que termino envia las cosas, para que actualice el listbox de las provincias cuando se cambie el pais se necesita recargar la pagina completa. Para realizar esto y no tener que depender ni de uno ni del otro esta AJAX, la verdad no te puedo dar ninguna información sobre esto ya que no se nada, pero si investigas seguramente te servira
Saludos.