I searched all over Google for the answers for this and most of them read that the PSU is at fault, but I did the paper clip test where you connect the green wire to one of the black wires (ref: http://aphnetworks.com/lounge/turn_on_psu_without_motherboard_the_paperclip_trick) and the fan spins.
So I thought my mobo was having problems, so I returned it, got a new one and I get the exact same problem. So I don't think it's the mobo at fault.
Update
I placed the motherboard over an anti-static grey clear bag (the one that you get for free when you buy a motherboard) just in case the case was shorting the motherboard, unplugged everything except for the RAM and CPU, and the same thing happens – it turns on for a second (I can see the fan spin) and then shuts down immediately. Keyboard and screen are not even attached.
Update 2
I found the solution to my problem. I posted it below.