How can an ISP program an AVR over SPI if there is no code on the device?
A fresh AVR, while it has no code programmed into the user space, doesn't mean it has no capability.

You'll notice that the RESET line is used as part of the ISP protocol. While the RESET line obviously does what you'd expect for most of the chip, it also enables the mechanism that handles the ISP. It also clearly delineates 'normal' operation from ISP operation, you are in one, or the other. You'll also notice there's a handshake of 'magic bytes' for the programmer to establish that this mechanism is working.

Whether this extra mechanism does all the work to handle protocol and control the memory busses, or whether it just flips an address line to allow the main CPU to run ISP code from a ROM (sounds more sensible?), doesn't really matter from the programmer point of view.