Simply going for multiple USB HDDs seems to be the obvious option (cheap, extendable, can be stored offsite and offline, etc.). However what would be some good Free Software to actually handle the backup? Common solutions such as duplicity, rsync, rdiff-backup, etc. all seem to assume that your backup target directory can hold the whole backup all at once and that the whole backup is online at the same time. While one can probably hack something together with union mounts to accomplish that, it seems like a very cumbersome and fragile solution.
Is there anything that allows you to just copy the data to a HDD and then plug-in a new one when the old one is full? Preferably in a data-format that is robust enough to handle some backup HDDs dieing without destroying the data on the other drives (i.e. no incremental changes across HDDs).