Since you say your grub bootloader appears, but the menu is empty, I think you don't need to reinstall grub, but rather, as you ask, run update-grub. To achieve this, you can use a Live CD, mount the relevant partitions from your hard disk, chroot into the mounted directory, and run update-grub, which should work as if you were operating on the actual hard disk.
Boot with your Live CD, selecting "Try Ubuntu without installing".
Once it boots, open a terminal (ctrl-alt-t) and mount your Ubuntu partition on /mnt. I'm assuming the Ubuntu partition is /dev/sda5, but you should determine this yourself. Let me know if you need help to do this:
sudo mount /dev/sda5 /mnt
Then mount a few more directories that are needed:
sudo mount --bind /dev /mnt/dev
sudo mount --bind /sys /mnt/sys
sudo mount --bind /proc /mnt/proc
Also, if you have a separate Ubuntu boot partition (pretty uncommon these days, but it may be the case):
sudo mount /dev/sdaX /mnt/boot
How can you tell if you have a boot partition?
Once you have your Ubuntu partition mounted, open /mnt/etc/fstab. If you see an entry for /boot, note which device it is pointing to (/dev/sda4 maybe?). This is the one you have to mount.
Once these are mounted, do chroot to start using the mounted directory as the root partition:
sudo chroot /mnt
You'll get a #/ prompt. First thing to do is confirm that you're using the correct /boot directory. Go to /boot/grub and look at the files there. There should be a bunch of .mod files and a grub.cfg file. If the directory is empty, don't continue, because it means this is NOT your actual boot directory. Look above to see how to determine if you need to mount an additional boot directory.
Once you've confirmed that /boot/ contains the correct files, meaning that it is the correct location, type:
sudo update-grub
This should rebuild your /boot/grub/grub.cfg file with the menu entries.
Then exit the chroot:
exit
At this point you may want to check that things were correctly updated. For this, cd /mnt/boot/grub and check that grub's files are there, there should be a bunch of .mod files and grub.cfg, the latter should have entries for your Ubuntu kernels. If you only see grub.cfg and no .mod files, it means that this is NOT the correct boot directory, look above for how to mount a separate boot partition.
Unmount the filesystems:
sudo umount /mnt/dev
sudo umount /mnt/sys
sudo umount /mnt/proc
sudo umount /mnt/boot #Only if you mounted it earlier
sudo umount /mnt/
And then reboot, hopefully your Grub menu will be restored.
