Attiny13 affects USBtiny programmer logic voltage levels
Well, after around 6 or 7 hours of dealing with this I finally solved it when I started playing around with a high voltage programmer. I hope this can help someone in the future.
The problem was that the Attiny13 came with the fuse bits set wrong. They were F6 F8, which meant that ISP programming was disabled (SPIEN bit unprogrammed). To make matters worse the lock bits seem to have been set, preventing me from writing the correct fuse values, even with the high voltage programmer.
Luckily I stumbled online with someone who had the same issue and mentioned having to perform a chip erase (which clears the lock bits but doesn't affect the fuse bytes) and only after that write the fuse values.
The resources which helped me were the following:
Thread with similar issue on arduino forum
High voltage programmer schematic (To be honest I didn't use the transistor and ditched all resistors save for the one from the 12V supply to the reset pin)
Post explaining this very same issue
Arduino code from said post (I recommend reading the post, but the TLDR is uncomment the chip erase lines of code to deal with the lock bits issue)