Permission issues when doing system backup using rsync
I'm trying to backup my linux system (arch linux on a laptop) to a remote computer on the same network using ssh (or NFS). I use rsync extensively to backup my /home directory to the remote computer over ssh and NFS with no issues whatsoever. What I want to do is run the rsync command on the laptop within a script and copy all of the contents of / (excluding some directories of course, that I already have figured out) to the remote computer.
The issue I'm having is about permissions. I have disabled root login on the ssh server (openssh, running on an ubuntu server 12.04 computer) and I disabled password authentication and enable rsa key login so I can run the backup scripts automatically using cron on the laptop. Now, for me to able to copy all of the system's files under /* (on the laptop) I need to run rsync as root. Doing that introduces a problem since I'm not able to access the ssh server as root. If I try to do it over NFS i get another permision problem since the root user isn't allowed to access the NFS mount, as my regular user is.
I'm writting here so I can get suggestion on how to solve this problem. I would prefer to do it over ssh since it usually works a lot faster for me, but I'm willing to use NFS or even samba (haven't tried that one) if no other thing works.