Problemas con PHP

$code = rand(1,9999);

while (mysql_query("SELECT id FROM usuarios WHERE Codigo = '$code'")) {
$code = rand(1,9999);
}

Con eso creo que podrias hacer tu el resto !
PD: no lo he probado asi que puede que haya algun error por ahi, pero es un concepto

while(mysql_result(mysql_query("SELECT COUNT(*) AS num FROM tabla WHERE Codigo='$codigo'"),0,"num") != 0) {
$codigo = rand(1,9999);
}

De todas formas los campos con la propiedad AUTO_INCREMENT se crean con el siguiente codigo valido sin que te haga falta asginar un codigo antes de grabar una fila.