rewrite get parameter with custom post type

I am trying now for a couple days to solve the following Problem:

I have a custom post type called gallery. I need the URL

http://example.com/gallery/FOOBAR

to be parsed like

http://example.com/gallery/?param=FOOBAR

The Permalink Setting for custom post type is:

/gallery/%postname%/%year%/%monthnum%/%day%/

I think I have tried about every code snipped that I could find to solve this problem but nothing seems to work.
If I flush all rewrites, none of my links work anymore (404)

Is is even possible?

I think it should work. First you need to register your rewrite rule and the parameter:

function my_init() {
    add_rewrite_rule(
        'gallery/(.+?)/?$',
        'index.php?post_type=gallery&param=$matches[1]',
        'top' );
    add_rewrite_tag('%param%','([^&]+)');
}
add_action('init', 'my_init');

Then you can read the parameter value from the query:

$param = get_query_var('param');

Don’t forget to flush the rewrites. (just view the rewrite settings page to flush the rules)