Hola:
Sin recargar la página solo puede ser con ajax, o cargando todas las listas de ciudades, pero no sería muy eficiente (en mi opinión)...
Con ajax (si te interesa la opción avísanos para pedir que muevan el mensaje, o hazlo tú pinchando en el triángulito de advertencia del mensaje...) necesitarías una página intermedia del lenguaje que soporte tu servidor, y que devuelva un documento xml (preferentemente) con las ciudades... luego se lee con ajax...
Bueno, dinos que te parece... recargar la propia página también es posible y no dependerías de ajax (y javascript por supuesto)
Saludos
