Hej Dontzi, perfect! I got the exact same problem, followed your instructions, and got the Oculus Setup 1.3 installed properly.
I am using an new ASUS Oculus-ready machine with Windows 10 (64bit), and out of the box I had both "Microsoft Visual C++ 2015 Redistributable (x64)" and "Microsoft Visual C++ 2015 Redistributable (x86)" installed on the machine, which seemed to have caused the error ("failure") according to the OculusSetup.log in C:\Users\<yourUser>\AppData\Local\Oculus (make sure to tick the option to view "Hidden items" the the Windows explorers "View" tab, because AppData is a hidden folder):
[Debug] [07/04/2016 09:47:02] Installing 'Visual C++ 2015' redistributable.
[Debug] [07/04/2016 09:47:03] Process C:\Users\<userName>\AppData\Local\Temp\OculusSetup-25263e4c-3383-4526-ba58-bdd237ae39b1\visual-cpp-2015.exe exited with code 1638 (failure).
[Debug] [07/04/2016 09:47:07] Exiting with code 1.
After that, I manually uninstalled both of the above mentioned Visual C++ 2015 Redistributables from the "Apps & features" system settings, restarted the machine and started the Oculus Setup again. This time with success.
So, I can confirm that this workaround seems to work. Make sure to search for the keyword "failure" within the OculusSetup.log, because it will not be flagged as an [Error] as in some other cases.