Looking into NAND Flash memory
NAND flash is not, generally speaking, suitable for use with an ATtiny. Use a SPI serial flash chip with this microcontroller.

NAND flash chips are not usable in practice without a translation layer. A NAND flash chip will typically contain some number of bad blocks. This particular chip is guaranteed to be delivered with no more than 80 bad blocks per 4 Gbit, for instance. Keeping track of these bad blocks is the responsibility of the controller; however, with only 512 bytes of memory (!), this is going to be essentially impossible on an ATtiny85. (You don't even have enough memory to read a single page of the flash chip into memory!)