Can no-connect pins on EEPROM ever be connected to VCC or GND?
The datasheet of the AT28C64 makes it pretty clear: There are "No Connect" (NC) pins, those are not connected in the chip so you can hook them up to a voltage. There are also "Don't connect" (DC) pins which you shouldn't connect but the DIP package doesn't have any of those. That's the obvious part.

The not so obvious part is that there are multiple versions of the AT28C64 and some of them have a READY output instead of a NC on pin 1. To avoid shorting things out, you should put a 330 Ohm (or so) resistor in series with pin 1 of the EEPROM so that if you plug in an AT28C64 with a READY output, the current gets limited.

With that resistor in series with pin 1, swapping in an 8K ROM instead of the 32K one should work just fine.