There are several ways, here's one. Does require either a flash or usb ext. drive or a 2nd cdrom that can write to a cd . (I think usb/flash is quicker and easier.
Take the livecd you installed Xubuntu 8.04 with and boot up to the livecd on a box with internet. (you pick the try without changing..., option.
Go to System, Admin..., software sources, ubuntu software and uncheck the cdrom box (1st. 4 boxes should be checked.
Because your on 8.04 there are medibuntu versions of some of needed packages. Before installing vlc add medibuntu as a repo. See below for how.
Then install vlc and anything else you want. When done go to places -> computer -> filesystem -> /var/cache/apt/archives. Copy all the .debs or just copy the archives folder itself. There'll be a pop up copy error box, click 'skip all' and then don't worry about it. ( if you copy the whole folder.
Transfer the folder to the other box and put in home folder.
From the terminal (use name of folder, showing 'archives'
cd ./archives && sudo dpkg -i *.deb
When your done you can delete the archives folder in home.
to add medibuntu, libdvdcss2, in a terminal
sudo wget http://www.medibuntu.org/sources.list.d/hardy.list --output-document=/etc/apt/sources.list.d/medibuntu.list
sudo apt-get update && sudo apt-get install medibuntu-keyring && sudo apt-get update
sudo apt-get install libdvdcss2