Apparently Google synchronized various data without my explicit permission. I don't want Google (and any parties that will ever have access to their data) to fetch any of my personal data without me allowing it!
Now I would like to at least transmit to them to delete it. How can I do that? I didn't find anything in the Google Dashboard. And there's no option to delete under Settings->Accounts->Google where I expected to find such a setting.
Back up your contacts on phone using any app from play store ( see Restore: Any Solution?)
(also note the contacts app has an export and import function built-in, so you won't necessarily need any 3rd party app for that)
Do the same for other synchronized data you want to keep (e.g. calendar; no built-in solution here, but you might pick an app from Izzy's list)
Disable Google Sync on your phone Setting → Accounts → Google including Gmail ( on Marshmallow, may vary on other versions)
Repeat that for other affected data (calendars etc.)
Remove Gmail account from your phone and use web version of Gmail from Chrome or any other browser to prevent Gmail contacts getting synced again ( In earlier Android versions you could selectively stop contacts from syncing but I have noticed that contacts sync even if you specifically don't want them to )
If you disable backup (under settings) - none of the apps you installed will be backed up adding to cutting off from Google.