Ok, I managed to install Matlab R2016a. I'm posting what I did in case anyone in the future needs this.
The culprit is Visual C++ Redistributable 2008, which Matlab wants to install at all costs (even though I wasn't even going to use it). I downloaded from the Microsoft website all Visual C++ versions, and all except the last one (2015 version) refused to install (same error).
I unpacked Matlab's setup.exe and inside the bin
directory I found the Visual C++ installer. There were two copies:
bin\vcredist_x64.exe
bin\vc90\vcredist_x64.exe
The latter is the one that was being executed, so I replaced it with the last version (I also had to rename the file in order to replace the Matlab's one).
Now the install went through, but when starting Matlab the Visual C++ 2008 kept popping up asking to install. So I went into Matlab's bin
directory (for me it was C:\Program Files\Matlab\bin
) and replaced vcredist_x64.exe
(which somehow Matlab had overwritten with its copy) with a custom executable which I compiled to do nothing at all.