Je ne pense pas que ça puisse être plus propre que ça :
ORDER BY priority=0, priority
Démo SQLFiddle
Notez que contrairement à toutes les autres solutions, celle-ci tirera parti de l'index sur la priority
et sera rapide si le nombre d'enregistrements est important.