Is it possible to get contacts from stolen iPhone 3GS?
You have a few options.


Restore from backup to another iPhone. If you do not have access to another iPhone, but have a backup file through iTunes locally on your computer, there are applications that can process those backup files. You may have success in browsing through them.
If you were using iCloud, then your contacts may have been syncing there. Login at http://www.icloud.com/ to see if they are there. Perhaps you had contacts syncing with another account, like one you used for email? Check there.