Undeletable EEPROM or other storage for micocontrollers?
Yes -- what you are after exists, at least for small sizes.  While most OTP EPROMs are parallel devices designed to be "burned" in dedicated EPROM programming hardware, Maxim makes exactly the part you're after in the form of the DS2505 -- 16kbits of in-system programmable OTP EPROM, with a unique serial number lasered into the chip as well that can be used to thwart chip replacement attacks.

You'll need a wee bit of drive circuitry as well as some bit-banging code to talk 1-Wire as the DS2505 requires its Vpp pulse to be muxed onto the 1-Wire interface along with normal power and data.