asi es, si extrae un registro quiere decir que ya existe algo como eso, con lo que tendria que generar otra serie de las que estas generando. Y para eso unicamente tendria que cambiar de lugar el while o cambiar lo por un do while()
Código PHP:
do{
$gen_string = generar_cadena(8);
$strQuery ="SELECT string FROM insertar WHERE string = $gen_string";
$sihay = mysql_query ($strQuery);
$verifica = mysql_num_rows($sihay);
}while ($verifica != 0);
suerte