1. Всю машину целиком. Гуглите gentoo stage 4, я таким образом сохраняю и таскаю образы чего угодно(Gentoo, Debian/Ubuntu, RedHat) между любыми хостингами. Чуть правлю файл в котором описываем что не включать в архив. Сделали машинку, настроили, сделали ей stage4.
2. Хранение данных. Изменяемые данные бэкапить отдельно от образа машины. Что бы вы могли в какой-то момент поднять ее из образа и накатить все что было. В зависимости от БД и содержимого смотрите, тупо mysqldump по крону и /srv/www по крону, к примеру заворачивать в архив и бэкапить.
3. Место. Если аккуратно к нему подходить, то амазон S3 выйдет в копейки. Либо взять еще пару VPS куда сливать и удалять лишнее.
Вот тупые решения которые могут помочь.