How to have this permalink structure: post_type/postname/custom_inner_page

Register your taxonomy first and set the argument slug and rewrite rules to your slug which is city

Register your post type with slug of your taxonomy city prefixed and make sure you set the has_archive argument to taxonomy.

Now add a filter to post_type_link to make the stores show the individual permalink.

register_post_type(
    'city',
    array(
        'rewrite' => array( 'slug' => 'city/%stores%', 'with_front' => false ),
       'has_archive' => 'city',
       // additional args
    )
);


register_taxonomy(
  'stores',
  'city',
   array(
    'rewrite' => array( 'slug' => 'city', 'with_front' => false ),
    // your other args...
)
);

function yourprefix_store_permalinks( $post_link, $post ){
  if ( is_object( $post ) && $post->post_type == 'city' ){
      $terms = wp_get_object_terms( $post->ID, 'stores' );
      if( $terms ){
          return str_replace( '%stores%' , $terms[0]->slug , $post_link );
      }
  }
  return $post_link;
}
add_filter( 'post_type_link', 'yourprefix_store_permalinks', 1, 2 );

Use built-in Tools Generating WP Stuff here at GenrateWP

Hope this is what you are looking for. If not you can read about similar article by https://wordpress.stackexchange.com/questions/199456/custom-taxonomy-post-slug-permalink