Keep old post URLs after changing permalink settings

My permalink settings used to be “Date and Name” which corresponds to:
/%year%/%monthnum%/%day%/%postname%/

Now I’ve updated the permalink structure to this format:
/%custom_taxonomy%/%postname%/

I have solved the %custom_taxonomy% part by using filter hooks post_link and post_type_link. (The URL/permalink is only updated after the user has selected a custom taxonomy term)

The new URL’s are working as intended, but I’m facing a new problem.. the old URL’s stopped working. Now WordPress is trying to rewrite these urls:
/2015/09/10/my-china-trip/
into:
/%custom_taxonomy%/my-china-trip/
which generates a “Bad Request”.

How do I force WordPress to still display old posts using the old format while also displaying the new format?

I cannot create 301 redirects as the old posts do not have a %custom_taxonomy% set and updating all old posts is not an option.

Thanks!