Since the same chip worked fine in other UNO board, the bootloader is not the issue. I went and shoved a 16MHz clock into the socket as suggested above (fortunately I have small DIP oscillator with 0.1" spacing) On first try, it worked. The chip responded and I was able to upload blink sketch.
I'll probably leave it like that and get a case to protect the oscillator from coming out.