Electronic – Problem with I2C EEPROM communication

You're reading the data after clock is low again. You'll have to do that between making the clock high and making it low. After the clock is low the slave is allowed to change the data line, not while it's high.

So reading should be like this:

wait
SCL low
SDA high
for each bit (8 bits)
    SCL high                      <--------
    wait
    check and store received bit  <--------
    wait
    SCL low                       <--------
    wait
    wait
do a NACK or ACK depending on if it is the last byte

1) What happens when the I2C pullups are omitted?

There will be no communication on the I²C bus. At all. The MCU will not be able to generate the I²C start condition. The MCU will not be able to transmit the I²C address.

Wondering why it worked for 3 months? Read on.

2) The lack of pullups is likely to damage any of those two ICs in my board?

Probably not. In this particular case (MCU, RTC, nothing else), definitely not.

3) Why was the MCU able to communicate with the I²C slave device in the first place? I²C requires pull-up resistors. But they weren't included in the schematic.

Probably, you have internal pull-ups enabled on the ATmega. From what I've read¹, ATmega have 20kΩ internal pull-ups, which can be enabled or disabled from the firmware. 20kΩ is way too weak for the I²C pull-up. But if the bus has a low capacitance (physically small) and communication is slow enough, then 20kΩ can still make the bus work. However, this is not a good reliable design, compared to using discrete pull-up resistors.

¹Not an ATmega guy myself.

update: In response I²C waveforms, which were added to the O.P.
The waveforms in the O.P. have a very long rise time constant. Here's what I²C waveforms usually look like

PIC18F4550, Vcc=+5V, 2.2kΩ pull ups. Waveform shows SCL. The rise time on SDA is about the same. The physical size of the bus is moderate: 2 slave devices, PCB length ≈100mm.