There are 2 points of attack to cover when you are adding custom post type rewrite rules:

Rewrite rules

This happens when the rewrite rules are being generated in wp-includes/rewrite.php in WP_Rewrite::rewrite_rules(). WordPress allows you to filter the rewrite rules for specific elements like posts, pages and various types of archive. Where you see posttype_rewrite_rules the posttype part should be the name of your custom post type. Alternatively you can use the post_rewrite_rules filter as long as you don’t obliterate the standard post rules too.

Next we need the function to actually generate the rewrite rules:

// add our new permastruct to the rewrite rules
add_filter( 'posttype_rewrite_rules', 'add_permastruct' );

function add_permastruct( $rules ) {
    global $wp_rewrite;

    // set your desired permalink structure here
    $struct="/%category%/%year%/%monthnum%/%postname%/";

    // use the WP rewrite rule generating function
    $rules = $wp_rewrite->generate_rewrite_rules(
        $struct,       // the permalink structure
        EP_PERMALINK,  // Endpoint mask: adds rewrite rules for single post endpoints like comments pages etc...
        false,         // Paged: add rewrite rules for paging eg. for archives (not needed here)
        true,          // Feed: add rewrite rules for feed endpoints
        true,          // For comments: whether the feed rules should be for post comments - on a singular page adds endpoints for comments feed
        false,         // Walk directories: whether to generate rules for each segment of the permastruct delimited by "https://wordpress.stackexchange.com/". Always set to false otherwise custom rewrite rules will be too greedy, they appear at the top of the rules
        true           // Add custom endpoints
    );

    return $rules;
}

The main thing to watch out for here if you decide to play around is the ‘Walk directories’ boolean. It generates rewrite rules for each segment of a permastruct and can cause rewrite rule mismatches. When a WordPress URL is requested the rewrite rules array is checked from top to bottom. As soon as a match is found it will load whatever it has come across so for example if your permastruct has a greedy match eg. for /%category%/%postname%/ and walk directories is on it will output rewrite rules for both /%category%/%postname%/ AND /%category%/ which will match anything. If that happens too early you’re screwed.

Permalinks

This is the function that parses the post type permalinks and converts a permastruct (eg ‘/%year%/%monthnum%/%postname%/’) into an actual URL.

The next part is a simple example of what would ideally be a version of the get_permalink() function found in wp-includes/link-template.php. Custom post permalinks are generated by get_post_permalink() which is a much watered down version of get_permalink(). get_post_permalink() is filtered by post_type_link so we’re using that to make a custom permastructure.

// parse the generated links
add_filter( 'post_type_link', 'custom_post_permalink', 10, 4 );

function custom_post_permalink( $permalink, $post, $leavename, $sample ) {

    // only do our stuff if we're using pretty permalinks
    // and if it's our target post type
    if ( $post->post_type == 'posttype' && get_option( 'permalink_structure' ) ) {

        // remember our desired permalink structure here
        // we need to generate the equivalent with real data
        // to match the rewrite rules set up from before

        $struct="/%category%/%year%/%monthnum%/%postname%/";

        $rewritecodes = array(
            '%category%',
            '%year%',
            '%monthnum%',
            '%postname%'
        );

        // setup data
        $terms = get_the_terms($post->ID, 'category');
        $unixtime = strtotime( $post->post_date );

        // this code is from get_permalink()
        $category = '';
        if ( strpos($permalink, '%category%') !== false ) {
            $cats = get_the_category($post->ID);
            if ( $cats ) {
                usort($cats, '_usort_terms_by_ID'); // order by ID
                $category = $cats[0]->slug;
                if ( $parent = $cats[0]->parent )
                    $category = get_category_parents($parent, false, "https://wordpress.stackexchange.com/", true) . $category;
            }
            // show default category in permalinks, without
            // having to assign it explicitly
            if ( empty($category) ) {
                $default_category = get_category( get_option( 'default_category' ) );
                $category = is_wp_error( $default_category ) ? '' : $default_category->slug;
            }
        }

        $replacements = array(
            $category,
            date( 'Y', $unixtime ),
            date( 'm', $unixtime ),
            $post->post_name
        );

        // finish off the permalink
        $permalink = home_url( str_replace( $rewritecodes, $replacements, $struct ) );
        $permalink = user_trailingslashit($permalink, 'single');
    }

    return $permalink;
}

As mentioned this a very simplified case for generating a custom rewrite ruleset and permalinks, and is not particularly flexible but it should be enough to get you started.

Cheating

I wrote a plugin that lets you define permastructs for any custom post types, but like you can use %category% in the permalink structure for posts my plugin supports %custom_taxonomy_name% for any custom taxonomies you have too where custom_taxonomy_name is the name of your taxonomy eg. %club%.

It will work as you’d expect with hierarchical/non-hierarchical taxonomies.

http://wordpress.org/extend/plugins/wp-permastructure/