Good news. The CPU wasn't damaged after all. The RES (Reset) pin was bent inwards. To bad I didn't make a photo to show how that looked like.
Anyway, with the RES not connected to either ground or +5V the CPU would act entirely random and unpredictable. It would even change behaviour it I brought a finger close to side of the chip where the RES pin is located. Which was very weird.
With the RES pin connected the CPU started to act predictable. Only the address bus was still acting strange. Looking closer I noted that I have all the Arduino lines connected the wrong way around. After I fixed that the reset sequence went trough just as shown in the video.
The next thing to do is replace the 1kΩ resistors encoding hex EA on the data bus with an actual ROM so we can execute some real programs.
I'm also tempted to add an simple disassembler to the monitor program to get some easier to understand output.