Merge existing iPhone contacts to my iCloud
I found a solution. I was lucky and actually had contacts in my Gmail account separate from my iCloud (no overlap or duplicates between the two). So I just exported from Gmail in vCard form and then used the iCloud web interface (www.icloud.com) to import them into my Contacts. Everything is working great now.