1. You would have to get them off the other phone.
2. If you had the original phone synced to say a Google or Gmail account, you 'may' find the information for the contacts there. As long as it was actually synced regularly.
3. Should neither of the above apply, then you can always check your cell bill (either a paper copy or through your account on the carrier/service providers site). While it won't list the names, it will give you phone numbers, plus the date and time of calls. They may also list text data so phone numbers with their dates and times and possibly email addresses if the text came or went to one. While this route is a bit of a pain, it can get you some of the information you need.