Solved my own problem, yippee!
Bash script included below (for Debian Wheezy). Please read it before running it - I'm not responsible if it sets your server on fire etc. It should probably be commented, but...
#! /bin/bash
apt-get install -y advancecomp genisoimage
cd /tmp/tcl
wget http://distro.ibiblio.org/tinycorelinux/6.x/x86_64/release/CorePure64-6.1.iso
mv CorePure64-6.1.iso corepure64-6.1.iso
mount corepure64-6.1.iso /mnt -o loop,ro
cp -a /mnt/boot /tmp/tcl
mv /tmp/tcl/boot/corepure64.gz /tmp/tcl
umount /mnt
mkdir extract
cd extract
zcat ../corepure64.gz | cpio -i -H newc -d
cat >> opt/bootlocal.sh <<CONF
sudo mount /dev/hda2 /mnt
sudo mount --rbind /dev /mnt/dev
sudo mount --rbind /proc /mnt/proc
sudo mount --rbind /sys /mnt/sys
sudo LANG=C chroot /mnt update-grub
sudo LANG=C chroot /mnt grub-install --modules="biosdisk part_msdos" /dev/hda
sudo mount /dev/sda2 /mnt
sudo mount --rbind /dev /mnt/dev
sudo mount --rbind /proc /mnt/proc
sudo mount --rbind /sys /mnt/sys
sudo LANG=C chroot /mnt update-grub
sudo LANG=C chroot /mnt grub-install --modules="biosdisk part_msdos" /dev/sda
sudo mount /dev/vda2 /mnt
sudo mount --rbind /dev /mnt/dev
sudo mount --rbind /proc /mnt/proc
sudo mount --rbind /sys /mnt/sys
sudo LANG=C chroot /mnt update-grub
sudo LANG=C chroot /mnt grub-install --modules="biosdisk part_msdos" /dev/vda
sudo poweroff
CONF
find | cpio -o -H newc | gzip -2 > ../corepure64.gz
cd ..
advdef -z4 corepure64.gz
mkdir newiso
mv corepure64.gz boot
cat > boot/isolinux/isolinux.cfg <<CONF
default corepure64
label corepure64
kernel /boot/vmlinuz64
append initrd=/boot/corepure64.gz loglevel=3
CONF
mv boot newiso
genisoimage -l -J -R -V tc-grub -no-emul-boot -boot-load-size 4 -boot-info-table -b boot/isolinux/isolinux.bin -c boot/isolinux/boot.cat -o install-grub.iso newiso
mv install-grub.iso /isos
cd ~
rm -r /tmp/tcl
EDIT: This uses the CorePure fork as I'm running 64-bit guests.