Con php non si può fare, a meno che prevedi tre pagine (scegli categoria - invia / scegli regione - invia / scegli città - invia).
Se vuoi tutto in una pagina nel modo che hai descritto (ovvero che facendo una scelta nel primo menu, vengono caricate le possibili scelte del secondo) l'unica strada è usare ajax.