Since you've only deleted /usr/lib/* and not /lib/*, you can probably recover. I think all the programs you critically need to recover your system only use libraries from /usr/lib.

Boot to a text login prompt. If the normal boot doesn't give you a login: prompt in text mode, boot with only minimum services. Press and hold Shift when your computer starts to show the Grub prompt; you need to press the key after the BIOS has initialized the keyboard but before Grub is loaded, which on some machines leaves only a small time window and may require several attemps. At the Grub prompt, press Down to highlight the single-user mode boot entry and boot that.

Once you have a command line, run apt-get --reinstall install PACKAGE1 PACKAGE2 … to reinstall the packages that have files in /usr/lib. You can run this shell snippet to get the list of names of packages to reinstall:

egrep -l '/usr/lib/[^/]*.so.' /var/lib/dpkg/info/a*.list |

sed -e 's!^/var/lib/dpkg/info/!!' -e 's!.list$!!'

Some package installation scripts may require libraries from other packages to be present, so you may need to run the reinstallations in a particular order. If you find that a package's installation scripts are trying to use a particular program, you can find out which libraries this program needs with ldd. For example, this indicates that python is missing three libraries that you need to reinstall:

$ ldd /usr/bin/python | grep 'not found'

    libssl.so.0.9.8 => not found

    libcrypto.so.0.9.8 => not found

    libz.so.1 => not found

dpkg -S /usr/lib/libz.so.1 reveals that this file comes from zlib1g, and so on.

If you find that apt-get is unable to download packages, first download a few key packages from a live CD. zlib1g and libssl0.9.8 are two packages you're very likely to need early on.