How to automatically generate a unique random slug

Use the function wp_unique_post_slug(). Do not reinvent the wheel, this one is quite tricky.

Usage:

$unique_slug = wp_unique_post_slug( 
    $slug,
    $post_ID, 
    $post_status,
    $post_type, 
    $post_parent 
);

Then you can test if $slug === $unique_slug and generate a new one if the test fails.

You can find the function in wp-includes/post.php. It ends with a filter 'wp_unique_post_slug', so you can still adjust the return value if you don’t like it.