Don't know how you have your system setup but I do the following (running Google Apps for Calendar, Contacts & Mail). Note that because Google is a better sync solution I do NOT use iCloud (except for Find My Phone) :
In Settings>Mail, Contacts, Calendars> select active mail account and turn ON the appropriate Sync buttons for the 3 items (your account may or may not support this)
In the actual Contacts app, you might have a "Groups" button top left corner. If so, hit it and select the version of your Contact list that you use to sync (in my case my account is called Exchange). Any changes you make to this contact list will automatically sync w Google.
Basically you want to ignore any of the "From My PC" lists that are created by iOS, as they are local only and will not externally sync via any cloud.
If this solution is not possible for you, I'd probably just migrate everything over to iCloud and dump your G-sync.