Restructuring permalink with more than one taxonomies

That’s quite possible by changing add_permstruct or filtering rewrite_rules. But what is your strategy for generating links for city? How will implement second taxonomy?

I would go for implementing this as rewrite rule for something like

add_filter( 'rewrite_rules_array', function( $rules ) {
    global $wp_rewrite;

    $new_rules = array(
        '(company|profession)/([^/]+)/([^/]+)/?$' => 'index.php?$matches[1]=$matches[2]&city=$matches[3]'
    );

    $rules = array_merge($new_rules, $rules);
    return $rules;
});

However, this isn’t optimal and you will need to generate the bunch of supported rules (paging feeds). But you still need to generate links for them and its up to you!

cheers.