Stavi operando nel modo sbagliato, al fetch devi passargli il risultato della query, se gli fai rieseguire ogni volta la query è ovvio che non finirà mai, ad ogni cilco ricomincia dall'inizio.
Si fa così (in pratica il secondo metodo che hai postato)
Codice PHP:
$query "SELECT * FROM regioni ORDER BY regione";

$result mysql_query($query); //così viene eseguita adesso e basta

while($regione mysql_fetch_array($result))
{
    echo 
'<option value="'.$regione[0].'">'.$regione[1].'</option>';