I'm just wondering if it would be possible to do it without the computer, using an arduino.
The Arduino is a computer. To answer your first question, it's impossible to have computer controlled christmas lights without a computer. By definition.
As far as your space limitations, it's not that hard to add an SD card to the arduino, it's in the playground under storage. But you can just add a 256kbit serial eeprom for $2. I2C EEPROM - 256k Bit (24LC256) - COM-00525 - SparkFun Electronics