Hi James. Please allow me to offer some clarifications:
A. server speed- too many 301 redirects is going to put an unnecessary load on the server and reduce speed =BAD
The concern is HOW the redirects are made. If your client has a URL www.oldsite.com, and he moves his entire 10k page site to a new URL, www.newsite.com, and he keeps his URL structure the same at the new site, then the entire re-direct can be done in a single line. In this case there is absolutely no additional load on the server.
Alternatively, if the new site structure is such that hundreds of rules need to be written to properly complete the re-directs, then yes, your speed can be impacted as each request requires the server to iterate through hundreds of lines of code to seek a match.
You shared there would be a change to the URL structure. Your 301 logic would depend on if the change follows a logical pattern to where a regex mapping can be created in a few rules.
B. being penalised- too many 301 redirects can be viewed as aggressive PR sculpting and your 301's can be devalued
C. Avoiding 301 redirect chains- Matt Cutt's interview with Rand in 2010 said 301 chains are not a good thing as a general rule
This refers to chain 301s, a practice that I do not use and would never advise. Go to the original site and ensure each page is properly directed to it's final location.
You can redirect all 100k pages of site A to site B and that would not be considered "too many redirects" nor page sculpting. When you re-direct from site A to site X to site Y to site Z then to site B (the final destination), that would be considered too many re-directs. This could happen even if the re-directs were within the same couple of sites. Even if the re-directs all worked, each hop is a leak in the link juice pipeline.
404's are not necessarily a bad thing
I agree, but a 301 is far superior IF you are keeping the content.
Let's say someone is looking for an article on the 1982 Corvette Stingray. He locates a search result, clicks on it and is taken to the article on your site. He is a happy search engine user, and now a happy visitor on your site. Everyone wins.
Using the same example, the person gets a 404 page on your site. There is an extremely high chance the user will simply return to Google and move on to the next result. Everyone looses.
404s should be used for content when it is highly unlikely a user will ever look for it in a search result OR if you no longer have the content. You would never want to 404 a link when you still have the content and know where it is located.
With all of the above noted, I agree with your plan. The pages with no value, meaning the pages are not searched for or you no longer have the content, can 404.