As above, many people do not realise the benefits of using a Google account, so do not set one up and course some are just paranoid so don't

If the phone was setup using a Google account then I'm sure that is the default save location for contacts, simply settings up the new phone using the same account will be enough to pull the contacts back in. If you go to
https://contacts.google.com and sign you should see your contacts. If he doesn't have a Google account then set one up and export the contacts to it, how easy that is depends on how old the phone is. Once you have the contacts in the cloud you can go to the Google contacts site and tidy them up, add address details, birthdays etc. With newer Android versions it is actually very easy to transfer a lot of stuff across to a new phone, you are given various options when setting the phone up.
For SMS and call logs I use SMS Backup & restore by SyncTech Pty Ltd.