How to store passwords securely in my server?

You face the problem every password manager faces. I believe that their solution is to use a symmetric algorithm to encrypt the sensitive data, and use a master password for each user to derive a decryption key for all his/her saved passwords. This master password will have to be entered every time your script/application is restarted or, in the case of a web application, every time the user logs in.

This is basically what you describe in your second bullet point. The cryptographic tool you need is PBKDF2: use this on the user's login password when it is sent. The resulting key should be suitable to encrypt/decrypt passwords in the database using MCRYPT_RIJNDAEL_256.

On a side note : make sure you use different initialization vectors each time you encrypt new data !