Actually, I'd recommend to use Dr. Azzys core instead. It supports most major ATtinys, including Attiny2313 and ATtiny4313. The core is always up to date, and if you have any issues, or finds a bug; he usually answer within a few hours. That core also got a working EEPROM library. Check it out at
You would have had to copy the entire EEPROM folder into (location of core's boards.txt)/libraries - architecture specific libraries like EEPROM need to be in the core's libraries folder. And indeed, my version is just a copy of the one from the default core. That seems to work for any AVR.
2k is really tight for Arduino - Arduino isn't that efficient with flash space, particularly at the low end, since there's a lot of stuff that requires a fixed amount of space (ie, to set up millis, and the code for digitalRead/digitalWrite, serial, etc).
There are other ATtiny's with serial - the ATTiny841 has 2 (there's also a cheaper 441), with 11 IO pins + reset and 3 timers (6 PWM pins), and the ATTiny1634 has 2 as well, with 17 IO pins + reset, 2 timers, and the 828 has one - and 27 IO pins + reset, ADC on every pin. Actually, all of these have ADC on all or most pins. Unfortunately they're all SMD only, no nice DIP packages - though I happen to sell breakout boards for them assembled and bare boards )