Debian/Ubuntu is it possible to reinitialize /var/lib/apt/lists and /var/apt/cache after deleting them?

Yes, you can delete them!

Let's clone a VM and see what happens! :)

$ rm -r /var/cache/apt /var/lib/apt/lists
$ apt-get update #takes a while re-fetching everything
$ apt-get install <some-random-package>

Directories are recreated from the apt-get update operation and all is well. I might leave the *.gpg files alone if you're feeling paranoid, but otherwise those files are all ok to disappear.

In the past, I've had issues where I've had to manually mkdir /var/cache/apt/archives, but that no longer seems to be an issue.

On Ubuntu 10.04 LTS the directories are not recreated. So you have to be careful not to delete these. You can use the following command to delete only the files.

sudo find /var/cache/apt/ -type f -exec rm -v {} \;
sudo find /var/lib/apt/lists -type f -exec rm -v {} \;

To recreate the cache use

sudo apt-get update

A better answer is probably Debian/Ubuntu - How to restore /var/cache/apt structure after deleting it?