If you both are syncing with iCloud, you need different Apple IDs to keep your contacts separate. Otherwilse one or both have to stop syncing contacts with iCloud (or other cloud service like Gmail)
Settings > iCloud > Contacts > Off
Note that the iTunes/App Store account ID is separate, and can be kept the same if you want to share apps and media.
You should use separate Apple ID's for iCloud, iMessage and FaceTime. These services are separate from iTunes.
Create a new Apple ID > https://appleid.apple.com/cgi-bin/WebObjects/MyAppleId.woa/ -- Note: You need a verified email address
On one of the devices go:
Settings > iCloud > (Scroll Down) Delete Account > Sign in with the new Apple ID -- Note: This only affects the device
Settings > Messages > Send and Received > Apple ID > Sign Out > Sign in with the new Apple ID
Settings > FaceTime > Apple ID > Sign Out > Sign in with the new Apple ID
This will separate your iCloud content (i.e. Contacts, Notes, Reminders etc.), Messages and FaceTime.
You both can continue to use the same Apple ID for iTunes and share purchased Apps, Music and Movies
If he creates a new apple id for icloud, he can still keep all the contacts he has right now. What he would do is delete the icloud account from the phone as the others instructed, but you would choose to 'keep info on phone' when it prompts you to. if he only wants to keep the contacts, and not necessarily other information that he previously had on icloud, or stuff you added for that matter since you were sharing an account, before he deletes the account, he would turn off the contacts slider, choose to keep the contacts on the phone, then delete the whole account and choose to remove the info from the phone. basically, it depends on if he wants all the info on his phone to still be there, or if he only needs the contacts