Custom post types, taxonomies, and permalinks

Change slug in your post type arguments to products/%product_cat%, and slug in your taxonomy arguments to just products, then flush your rewrite rules. WordPress should now handle /products/my-product-cat/post-name/!

Now finally, we need to help WordPress a little with generating permalinks (out of the box, it won’t recognise the permastruct tag %product_cat%):

/**
 * Inject term slug into custom post type permastruct.
 * 
 * @link   http://wordpress.stackexchange.com/a/5313/1685
 * 
 * @param  string  $link
 * @param  WP_Post $post 
 * @return array
 */
function wpse_5308_post_type_link( $link, $post ) {
    if ( $post->post_type === 'product_listing' ) {
        if ( $terms = get_the_terms( $post->ID, 'product_cat' ) )
            $link = str_replace( '%product_cat%', current( $terms )->slug, $link );
    }

    return $link;
}

add_filter( 'post_type_link', 'wpse_5308_post_type_link', 10, 2 );

One thing to note, this will just grab the first product category for the post ordered by name. If you’re assigning multiple categories to a single product, I can easily change how it determines which one to use in the permalink.

Lemme know how you get on with this, and we can tackle the other issues!