You could save half as often to achieve the same effect. Probably better still, do run-length encoding. You didn't say how often you save, but unless it is hours apart, the temperature and humidity are likely to be often the same. So you could do something like this...
Save: Count, temperature, humidity (3 bytes) whenever the temperature or humidity changes.
4 x temp=21 humidity=40 (ie. 4, 21, 40)
8 x temp=22 humdity=41 (ie. 8, 22, 41)
Since a single byte will hold 256 values that will hold the temperature (-100 to +150 is only 250 values) and the humidity percent (0 to 100).
If you were previously measuring (say) every minute, you might find a hundred readings overnight where it doesn't change. Of course, you need to detect if you get 255 identical readings and output a new one anyway. This method could save you hundreds of bytes, per day.
The other approach is to add in an external EEPROM. I did a write-up recently about a 32kB (256 kBits) EEPROM which is only in a DIP8 package which you talk to using I2C. Since you can do a million erase/program cycles anyway, and you will take a while to fill 32Kb, this should last quite a while. And when it starts wearing out, pull it out of the chip holder and replace it for $5 or whatever it costs. In fact I calculate that at the rate of writing 2 bytes (temp/humidity) per second, the 32Kb should last 519 years.
Bytes in chip: 32 * 1024 = 32768
A million rewrite cycles: 32,768,000,000
Using 2 bytes per second: 16,384,000,000
Divide that by 60 * 60 * 24 * 365 = 519.533
So if you are still around in 519 years, then you replace the chip!
For a description of doing this with I2C: http://www.gammon.com.au/forum/?id=10896