I can't see how the supply voltage is too high. First off, the voltage comes from USB and it goes through a regulator after that. Even if the voltage was too high, it wouldn't allow me to use the arduino with the standard DIP28 chip. I have measured it to 5.05V so the supply isn't the issue.
What I thought about was if several of the outputs were shorted to GND or +V (even thought I haven't found such a short), but I guess the outputs of the MCU is current limited? Also, what if I have a faulty crystal that has a higher frequency than what it says on it, can that create heat?
After talking about this issue on the freenode's #electronics chat, people seemed to start thinking that I've bought a bad batch of Atmega's. Thing is that the third chip I tried was taken from another project and the chip worked just fine on that previous project! And I also mentioned that I can burn the bootloader and upload code prior to soldering it to my PCB, the heating and errors occur after it is on the board. I guess I could try yet another chip
- - - Updated - - -
I solved it (I think)! While the chip was soldered to the PCB I checked if all the GND and +V pins were connected to the supply, and they were. To my suprice, when inspecting it while the chip was removed, GND pins 3 and 21 were not connected! I then checked Eagle and strangely enough, even though the schematic had wires going to these pins, they weren't actually connected
I can now upload the code, but I still don't know how this could have been the reason for it heating up though, nor do I know why it needs so many ground pins
edit: Never mind, the success was short lived. The same symptoms have started appearing on this chip as well, I can no longer upload any code.
edit: I figured out something. The heating of the last three chips came after I uploaded a code that communicates with an ADC using I2C. I tried to connect the PCB to the arduino and then upload a clean code straight away and it worked, it doesn't heat up if there is no code on the chip. This is somehow caused by trying to use I2C.