Perchè sei obbligato ad usare una sola query?
Nel codice che hai postato all'inizio mi pare che potevi usarne anche più di una...
Comunque in tal caso mi viene in mente solo la funzione UNION che si occupa di unire i risultati di più query ma in una sola.
Potresti fare una cosa del genere:
Codice PHP:
$query = "SELECT COUNT(DISTINCT(nazione)) AS cnazioni, DISTINCT(nazione) FROM location ORDER BY nazione ASC
UNION
SELECT COUNT(DISTINCT(regione)) AS cregioni, DISTINCT(regione) FROM location ORDER BY nazione ASC
UNION
SELECT COUNT(citta) AS ccitta, citta FROM location ORDER BY citta ASC"
Questa query quindi ti unisce i record delle nazioni, quelli delle regioni e delle città.
Dopo di che in ogni <select> fai un ciclo for per cnazioni quando lavori sulle nazioni, cregioni quando lavori sulle regioni e printi i risultati. (cnazioni e cregioni ti dicono rispettivamente quante nazioni e quante regioni ci sono)
PS. La query l'ho scritta ora senza provarla, dimmi se va.