How to add gallery slug to attachment url?

So I was able to make it work (without .htaccess as Tom sugested) using WordPress Rewrite API. Here is my working code (from functions.php):

function add_rewrite_rules( $wp_rewrite )
{
    $new_rules = array
    (
        '(the-gallery-slug)\/(.?.+?)(?:/([0-9]+))?/?$' => 'index.php?pagename=$matches[2]'
    );

    // Always add your rules to the top, to make sure your rules have priority
    $wp_rewrite->rules = $new_rules + $wp_rewrite->rules;
}

add_action('generate_rewrite_rules', 'add_rewrite_rules');

And here are links that helped me a lot:

“WordPress – wp_rewrite rules” post on stackoverflow

Debug WordPress 404 issues (permalinks, rewrite rules, etc.)