Credo che l'unico modo sia fare una serie di select a partire da uno salendo fino a trovarne uno nuovo.
Codice PHP:
$index = 1;
while(true)
{
   $query = "SELECT COUNT(id) FROM Tabella WHERE id = $index";
   $res = mysql_fetch_array(mysql_query($query));
   if(intval($res[0]) == 0)
      break;
   else
      $found++;
} 
Il problema è che potrebbe essere una cosa un po' pesante per il DB (specie se lo metti come funzionalità Front End)