Bought a brand new battery, but the problem persisted. Started looking at all the various parts in the car, that were connected to the electrical system. Took them out, troubleshooting the parts to my best ability, even ended up buying a new alternator AND solenoid just out of sheer desperation.
3 months went by, countless hours in the garage, and I thought to myself...could it be...could it be the new battery I bought? Bought yet another battery, and everything worked. Just like that.
Turns out the battery I had in my car originally had degraded, and couldn't store enough charge. And the second (brand new) I bought turned out to also be defect, having the very same fault.
Those faulty batteries would charge up to measure the correct voltage, but didn't get the correct charge capacity - and thus the car couldn't draw enough current to start the engine.
And don't get me started on the weird wacky world of electronics...but the car debugging was by far the longest I've spent, at one point I had almost every component out of the car, going over the wiring.