okay, I solved my problem. Here are the steps just in case anyone else wants to use the 'paramiko' library for a ST2 plugin:
1) use 'easy_install paramiko' to install paramiko and crypto. Now your system python should be able to import paramiko
2) Install paramiko for your ST2 plugin
a) Get paramiko from here
http://www.lag.net/paramiko/ (or alternatively the most recent version from github).
b) Place the folder with the '__init__.py' file in [ST Packages]/[MY PACKAGE]/paramiko
3) Install Crypto for your ST2 plugin
a) Check where your python libraries are using
python -c "from distutils.sysconfig import get_python_lib; print get_python_lib()"
b) Go to that folder (in my case /Library/Python/2.7/site-packages) and copy the file 'pycrypto-2.6-py2.7-macosx-10.8-intel.egg' somewhere
c) Unpack it (just rename it to .zip)
d) copy the Crypto folder with the __init__ file from the unpacked folder to [ST Packages]/[MY PACKAGE]/Crypto
4) Change line 28 in the file '../Crypto/Random/__init__.py' from 'Crypto.Random import OSRNG' to 'import OSRNG'
(Note: I think you have to go through the installed Crypto package and not just the downloaded one because that includes some compiled c libraries. So I guess you can also compile them yourself)
I know, it's a mess but now you should be ready to go. If anyone has an easier solution, please post. I think that these kind of things prevent a lot of non-professional developers from developing packages.