I've looked for incremental backups that don't require root before, but I finally found it. Similar to rdiff-backup is a program called duplicity. It uses tar, gpg, and the rsync algorithm to store encrypted differential backups.
duplicity needs to be scripted a little bit to automate the backups. I came up with a script that will backup certain directories fully once a week and incrementally the rest of the week. I also disabled the encryption since the transfer method is secure (ssh in my case) and the end server is trusted. If you were using Amazon's S3 service or a public FTP share you might want to tweak this a bit.
/etc/cron.d/backup
32 3 * * 1-7 root /usr/local/sbin/backup.sh cmd=full
32 3 * * 0 root /usr/local/sbin/backup.sh
/usr/local/sbin/backup.sh
#!/bin/bash
[ "$v" = "" ] && v="-v0 --no-print-statistics"
[ "$cmd" = "" ] && cmd=""
duplicity="duplicity"
opt="--no-encryption $v"
dest="scp://taonas@thor.home.silfreed.net"
maxage="1M"
dcmd_backup="$duplicity $cmd $opt"
dcmd_age="$duplicity remove-older-than $maxage $opt"
# backups
$dcmd_backup /etc $dest/etc
$dcmd_backup /var/log $dest/var-log
$dcmd_backup /home \
--exclude /home/silfreed/tmp \
--exclude /home/silfreed/src/silfreednet/tmp \
--exclude /home/silfreed/src/workspace \
--exclude /home/silfreed/src/mozdev/workspace \
$dest/home
mysqldump_dir=/tmp/mysqldump
mkdir $mysqldump_dir &&
chmod 700 $mysqldump_dir &&
mysqldump -u root -A > $mysqldump_dir/mysqldump.sql &&
$dcmd_backup $mysqldump_dir $dest/mysql
rm -rf $mysqldump_dir
# age out paths
for path in /etc /var-log /home /mysql; do
$dcmd_age $dest$path
done
