You don't sync directly between phones, you sync same account with a server on both phones. iCloud can (and I wonder if it is not already working unless you have disabled contact sync or are using different different AppleId), but also other accounts you might have added to settings->e-mail, contacts, calendar (you can add an extra iCloud account here too). If you have multiple accounts with contact information setup, you can select which ones to appear in the contact list, by clicking groups in upper left corner.