Código PHP:
SELECT habitacion.* FROM habitacion LEFT JOIN reservas ON habitacion.numero=reservas.numero
WHERE
habitacion.numero NOT IN (
SELECT numero FROM reservas WHERE
'$fechainicio' BETWEEN fecha_inicio AND fecha_fin
OR '$fechafin' BETWEEN fecha_inicio AND fecha_fin
OR fecha_inicio BETWEEN '$fechainicio' AND '$fechafin'
OR fecha_fin BETWEEN '$fechainicio' AND '$fechafin'
GROUP BY numero
)
ORDER BY RAND() LIMIT 1