I managed to resolve the issue following these steps:
1. Installing Python 3.4.3 on another computer (not even the same architecture)
2. Copying the Python34 folder from that other computer to the computer I broke
3. Running the uninstaller for Python 3.4.3
4. Reinstalling Python 3.4.3 normally as it is now removed correctly

I also replicated this error in 2.7.10 and fixed it with only slightly different steps:
1. Installing Python 2.7.10 on another computer (again, not even the same architecture as the broken computer)
2. Copying the Python27 folder from that other computer to the computer I broke
3. Running the repair tool for Python 2.7.10
4. Running the uninstaller for Python 2.7.10
5. Reinstalling Python 2.7.10 normally as it is now removed correctly

I replicated the issue in 2.7.10 again afterwards, and it does appear that step 3 is required.