Turned out we should get the raw contact id for insert:
ContentResolver resolver = getContentResolver();
Uri uri = Uri.parse("content://com.android.contacts/raw_contacts");
ContentValues values = new ContentValues();
long id = ContentUris.parseId(resolver.insert(uri, values));
uri = Uri.parse("content://com.android.contacts/data");
values.put("raw_contact_id", id);
values.put(StructuredName.GIVEN_NAME, given_name)
resolver.insert(uri, values);