Random Alphanumeric Key URLs

If you’d like to keep your slugs for SEO, then you’ll want to define a new rewrite tag and leave the default behavior for post slugs.

If you’d like a unique id, then instead of looking up possible duplicates, why not just re-use the post ID which is guaranteed to be unique given a MySQL primary index – you can convert it to a base36 number if you want it to look more like bitly.

add_action( 'init', function() {
    add_rewrite_tag( '%my_id%', '([a-z0-9]+)' );
});

add_action( 'pre_get_posts', function( $query ) {
    if ( ! $query->is_main_query() || is_admin() )
        return;

    $id = $query->get( 'my_id' );
    if ( ! empty( $id ) ) {
        $query->set( 'p', base_convert( $id, 36, 10 ) );
        $query->set( 'name', null );
    }
});

add_filter( 'post_link', function( $permalink, $post ) {
    $id = base_convert( $post->ID, 10, 36 );
    return str_replace( '%my_id%', $id, $permalink );
}, 10, 2 );

Then change your permalinks structure to /%my_id%/%postname%/ in Settings – Permalinks. If you want more than 0-9 and lowercase characters, you can look for some base 62 implementations, though I’m not a big fan of case-sensitive URLs.

Hope that helps.