Wordpress - 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!

Thanks @TheDeadMechanic, your answer helped me out, but only partially. I wanted to do the same thing @RodeoRamsey asked for, but with nested categories (ie: mysite.com/products/category1/child-category-1/grandchild-category-1/product-name) and your solution didn't work for that.

I finally came up with an extended solution to my question that works, so if anyone else needs nested categories/subcategories you can see a detailed solution on my own question. Hope it helps others, and thanks for the initial steps.

I'm not sure wp supports that structure out of the box - but you can very easily create your own rewrite rules to do so.

Check out a previous answer here Author url rewrite.

You can change the line

$newrules['author/([^/]+)/songs/?$'] = 'index.php?post_type=songs&author=$matches[1]';

to something like

$newrules['products/([^/]+)/([^/]+)/?$'] = 'index.php?post_type=product_listing&product_cat=$matches[1]&name=$matches[2]';

the product_cat part here may be superfluous - I am not sure if it is needed.

You can add any rules you like and they will have priority over the inbuilt ones.