It turned out that I had accidentally made the cache contents way larger than I thought. It may have been like 6GB at some point. This happened because my program was putting stuff in
$XDG_CACHE_HOME, and Netlify was caching it without my knowledge as the “pip cache”. I think it would be better to either cache only the pip directory or improve the logs to make it clear that it is potentially more than just the pip cache.
What’s weird is that my efforts of clearing the cache and rebuilding didn’t seem to have any effect. It felt like the cache was corrupt in some other way.
I started a new Netlify site (with the same sources) with a fresh cache and was able to get it all working.
Thanks for the help @fool! I hope this will help someone else as well.