Getting Post ID from slug during init

This is not really a WP_Rewrite question, unless you want to include the post ID in the URL. I think the best way to solve this is, as you suggest, do a get_posts() query with your slug, and change the variables from there.

Of course you don’t have to do this on every init, only do it when you are at a clubs/[club_slug]/news/ page. So first create a rewrite rule that will set a special variable that you can check:

add_action( 'init', 'wpse8421_init' );
function wpse8421_init()
{
    // Assuming `wpse8421_club` is the name of your custom post type
    add_rewrite_rule( 'clubs/([^/]+)/news/?$', 'index.php?wpse8421_club=$matches[1]&wpse8421_related_news=true', 'top' );
}

Add this query var to the public query vars so you can check for it:

add_filter( 'query_vars', 'wpse8421_query_vars' );
function wpse8421_query_vars( $query_vars )
{
    $query_vars[] = 'wpse8421_related_news';
    return $query_vars;
}

Then check for this extra variable, and if it is set, modify the query.

add_filter( 'request', 'wspe8421_request' );
function wpse8421_request( $query_vars )
{
    if ( array_key_exists( 'wpse8421_related_news', $query_vars ) ) {
        $club_posts = get_posts( array(
            'post_type' => 'wpse8421_club',
            'name' => $query_vars['wpse8421_club'],
        ) );
        if ( $club_posts ) {
            $query_vars['connected'] = $club_posts[0]->ID;
            unset( $query_vars['wpse8421_club'] );
        }
    }
    return $query_vars;
}