For the 74HCT04 -- try a 74LS04 if you have one. Not at all critical regarding brand or HCT versus LS.
For replacing IC's - I would have started with the cheaper parts such as the 74xx series parts.
As mentioned by BarakandI - the 74xx series parts (including 74HCT04) have max voltages of 7V, anything above that can take them out. 4000 series are more tolerant and can work up to about 15.
All the decode logic (Z9, Z10, Z12, Z7, Z8) as well as Z2 and Z3 are suspect. Plus the stuff hanging off U4 through U6 would be equally suspect.
Z1, Z4 and Z36 would have been less concerning.