That "full backup space" is of course still the gotcha — basically, you'll need a spare disk. However, external disks are increasingly cheap; and rsnapshot can be used remotely with ssh. So you could use one large central disk to keep snapshots of your most important data from multiple clients.
rsnapshot is relatively easy to configure. Check /etc/rsnapshot.conf for the minor edits needed (make sure to uncomment the "interval" lines), then try a test run from the command line with rsnapshot hourly. The interval names don't actually matter; they're just used to define how many snapshots of each type are kept. The actual run intervals are defined using the crontab — a reasonable crontab example is provided.
The first run may take a while (as always with a first run of rsync). Subsequent runs will be much faster as the files are updated from the snapshot. Usefully, it's possible to set it up so any user can pull his or her own backups, rather than relying on root access — thus minimizing your work later on!
rsnapshot should run on nearly any Unix-type system (requiring only perl and rsync), and is available as a package for most of the major Linuxes.