Rewrite custom post type with taxonomy

Regarding the code base rewrites, you should be using %city% instead of city, as custom taxonomy used in slug param for rewrites should be enclosed in %TAXONOMY%

WordPress should still be able to redirect your old posts from the old URLs to the new ones. Did you add the filter on the post_type_link?

If you’re doing this for a custom post type, you can use this plugin to customize the permalink in the core WordPress permalink configuration area:
https://wordpress.org/plugins/custom-post-type-permalinks/

There’s also this plugin:
https://wordpress.org/plugins/permalinks-customizer/

Which allows you to use custom taxonomies in your permalink structure tags.