Es gibt auch SD Libs die ein paar kB kleiner sind (sdFat oder tinyFat):
http://forum.arduino.cc/index.php?topic=230652.0
Auf sehr umfangreiche Funktionen wie sprintf() verzichten kann kurzfristig sinnvoll sein. Die Alternative mit strcat() und itoa() ist ca. 1.3kB kleiner! Wenn da noch viel mehr dazukommt schieben solche Optimierungen das Problem aber nur etwas auf.
Den Bootloader löschen und den Arduino mit einem ISP programmieren spart glaube ich 0,5kB. Aber das bringt nicht wirklich was.
Ansonsten eventuell auf dem Mega umsteigen. Preislich gibt es auch den Atmega1284 als günstige Alternative in der Mitte. Der hat 128k Flash und 16kB RAM (damit sogar mehr RAM als der Arduino Mega!) Aber das ist ein blanker Prozessor, den du auf einem Breadboard oder einer eigenen Platine betreiben musst.