Had the same foolish problem... here is what I have done to get everything working again:
1. Like in the answer of @Gilles, make a list of your packages:
grep -l '^/usr/bin/' *.list | sed 's/\.list$//' > ~/my_packages1.txt
2. Insert a Live CD with the same Ubuntu version, boot from that and copy your
/usr/bin directory. The partition with Ubuntu on my hard disk was mounted, so that is as easy as
cp -R /usr/bin /media/something/usr/bin
3. Now I couldn't use
pkexec, because I got the error message must be owned by uid 0 and have the setuid bit set. So I had to change that, by booting from GRUB into a root shell. (See here how to do this and on this german site for some pics.) Now:
mount -o remount,rw /
chown -R root:root /usr/bin
chmod a=rx,u+ws /usr/bin/sudo
chmod a=rx,u+ws /usr/bin/pkexec
Reboot into your normal Ubuntu system.
4. Reinstall your packages:
sudo xargs -a ~/my_packages1.txt apt-get install --reinstall
5. There were still many packages missing.
debsums helped my finding those packages for installing them manually. (Maybe with this step 1 and 4 are obsolete, but I haven't tried...)
sudo apt-get install debsums
# This lets debsums find packages with missing files, filters the package names and writes the unique ones to the file.
sudo debsums -cs 2>&1 >/dev/null | sed -e 's/\(.*\)from \(.*\) package\(.*\)/\2/' | uniq -u > my_packages2.txt
sudo xargs -a ~/my_packages2.txt apt-get install --reinstall