Permalinks when using Custom Post Type with static page for archive

Yes, it is possible, and it is done by creating the custom taxonomy, then creating the rewrite in the custom post type, and then adding a filter for post_type_link to edit the actual permalink. Once you have the code in place, you have to go Settings > Permalinks and hit submit to refresh everything.

add_action( 'init', 'register_custax_type', 0 );
function register_custax_type() {
    // Add new hierarchical taxonomy
    $labels = array(
        'name'              => _x( 'Types', 'taxonomy general name' ),
        'singular_name'     => _x( 'Type', 'taxonomy singular name' ),
        'search_items'      => __( 'Search Types' ),
        'all_items'         => __( 'All Types' ),
        'parent_item'       => __( 'Parent Type' ),
        'parent_item_colon' => __( 'Parent Type:' ),
        'edit_item'         => __( 'Edit Type' ),
        'update_item'       => __( 'Update Type' ),
        'add_new_item'      => __( 'Add New Type' ),
        'new_item_name'     => __( 'New Type Name' ),
        'menu_name'         => __( 'Type' ),
    );

    $args = array(
        'hierarchical'      => true,
        'labels'            => $labels,
        'show_ui'           => true,
        'public'            => true,
        'show_admin_column' => true,
        'query_var'         => true,
        'rewrite'           => array( 'slug'  => 'portfolio' )
    );

    register_taxonomy( 'type', array( 'portfolio' ), $args );
}

add_action( 'init', 'register_cpt_portfolio' );
function register_cpt_portfolio() {

    $labels = array( 
        'name'                  => _x( 'Portfolios', 'portfolio' ),
        'singular_name'         => _x( 'Portfolio', 'portfolio' ),
        'add_new'               => _x( 'Add New', 'portfolio' ),
        'add_new_item'          => _x( 'Add New Portfolio', 'portfolio' ),
        'edit_item'             => _x( 'Edit Portfolio', 'portfolio' ),
        'new_item'              => _x( 'New Portfolio', 'portfolio' ),
        'view_item'             => _x( 'View Portfolio', 'portfolio' ),
        'search_items'          => _x( 'Search Portfolios', 'portfolio' ),
        'not_found'             => _x( 'No Portfolios found', 'portfolio' ),
        'not_found_in_trash'    => _x( 'No Portfolios found in Trash', 'portfolio' ),
        'parent_item_colon'     => _x( 'Parent Portfolio:', 'portfolio' ),
        'menu_name'             => _x( 'Portfolios', 'portfolio' ),
    );

    $args = array( 
        'labels'                => $labels,
        'hierarchical'          => false,
        'description'           => 'Portfolios',
        'supports'              => array( 'title', 'revisions', 'editor', 'thumbnail' ),
        'public'                => true,
        'show_ui'               => true,
        'show_in_menu'          => true,
        'menu_position'         => 25,
        'menu_icon'             => 'dashicons-images-alt',
        'show_in_nav_menus'     => true,
        'publicly_queryable'    => true,
        'exclude_from_search'   => true,
        'has_archive'           => false,
        'query_var'             => true,
        'can_export'            => true,
        'capability_type'       => 'page',
        'taxonomies'            => array( 'type' ),
        'rewrite'               => array(
                                'slug'          => 'portfolio/%type%',
                                'with_front'    => false
                                )
    );

    register_post_type( 'portfolio', $args );
}

add_filter( 'post_type_link', 'portfolio_permastruct', 10, 2 );
function portfolio_permastruct( $link, $post ) {
    // Only update portfolio permalinks
    if( $post->post_type !== 'portfolio')
        return $link;

    // get terms, if none are returned, it's false and just returns
    if( $cats = get_the_terms( $post->ID, 'type' ) )
        $link = str_replace( '%type%', array_pop( $cats )->slug, $link );
    return $link;
}

A full walk through can be found here