You could use debootstrap, especially if you have a swap partition and enough room on that swap to start a new "/"
Or you could also enable booting from a tftp server (provided your NIC can do it) and you have the tftp/rarp/bootp/dhcp end of things tied up.
You could D/L the Debian base debs from potatoe and chroot into the new filesystem... and finish from there.
If you need more detail.
[link|http://twiki.iwethey.org/twiki/bin/view/Main/DebianChrootInstall|http://twiki.iwethey...bianChrootInstall]
Is a good place to start.
If you need more info email me at the below addy.