It is possible,
try setting up another machine with a lot of disk space (at least enough for the size of your VPS and a host OS). Once you have done this you should perform the following actions:
dd if=/dev/hda | ssh username@placetobackup "dd of=/directory_of_backups_on_ssh_server/backupfile.img"
After downloading the backup img from your server, put it on a (external) harddrive. Next launch an Ubuntu live disk. Create a new partition, on the hard drive you are going to put your system on. It should have the same size as your VPS is using.
Lets say this disk is called /dev/sda
Lets say our external disk with our backup img is called /dev/sdb
parted /dev/sda mklabel msdos
use cfdisk
to partition your drive /dev/sda
Next mount your harddisk to your live environment
mount /dev/sda /mnt
Next mount your sdb
mkdir /oldImage; mount /dev/sdb /oldImage
cd /oldImage
Next we copy everything with all rights to the new image
find . -xdev | cpio -pm /mnt
Next mount some folders :
mount --bind /dev /mnt/dev
mount --bind /proc /mnt/proc
mount --bind /sys /mnt/sys
Chroot yourself :
chroot /mnt
Install a kernel and setup grub :
apt-get install linux-image-2.6-amd64 grub
grub-install /dev/vda
update-grub
Make sure in fstab everything is correct
vim /etc/fstab
Next shutdown the system, boot from the hard drive we copied everything to.