You dismissed the most important piece: the first place to start is the redirects. It will take work, but probably not nearly as much as you think. It can be done in a more dynamic fashion assuming the data used for the URLs was pulled from the database. I just helped a website with over 2 million URLs of many different formats create these redirects. In this case it was ahead of time, but we can map it out together if you need help. I know this is time sensitive and no one has responded with an answer yet, so if you need a call ASAP let me know and I'll try to flex around your time. We'll also briefly cover other strategies you should implement to get back in good stead with Google.

If you could give an example of the old vs. the new link the answer could be more precise.

But in general, the first thing I would do would be to make a redirect rule: either in htaccess file or on server-side you need to tell that all of the old links now should lead to the new pages' URLs. This is done through 301 redirect (permanent redirect) which would mean that all of the old links would pass the link juice to the new ones and the search engine would re-map to the new ones after some time (depending on the tempo of crawling your website).

I would leave those redirect rules active for quite some time though: old backlinks would still be leading to the old URLs. If you see in your analytics service that you get a lot of traffic juice from one or more sources specifically, the best idea is to get in touch with the webmaster of that site and ask for old link to be replaced with the newer one.

Regards
Igor

There are never too many to redirect, no matter how many there are. 301 redirecting your old URLs is absolutely critical. Without those, no matter what you do, you will never reclaim any external link value pointed to those pages. It may not amount to much on a per-page basis, but added together it's probably pretty significant.

If the old URLs followed a consistent pattern and the new URLs do as well, a good programmer should be able to create global redirects on a site-wide level rather than having to do it on a page by page basis.