Unfortunately, contacts on a phone you no longer have would not be retrievable.
Had they be saved through Google, or another App/service, then you would have access to them.
I understand you said they were not properly synced, however did you ever save them to your Google account or another email? If so, then you would be able to retrieve them that way.
Another option that 'may' get you at least some of them back is to check your account with your carrier. Most keep records of numbers called and numbers texted to. You would be able to gain some of them back that way.
Other than these, I know of no way to get the information back, short of getting the phone back.