How do I cleanup all information backed up from my phone? i.e. I want to remove all information, that was backed up from my phone to the Google servers (sync data, etc). How can I do that?
Go to Google Dashboard and sign in with the same Google account you used on your phone. Click the arrow next to Android to see a list of all your devices with backup data. At the bottom is a button, Delete backup data. This button deletes the backed-up data from all devices. There's no way to delete the data from a specific device.

If you want to delete not only the data backed up using the "Back up my data to Google servers" option, but also other synced data like Gmail, contacts, calendars, Google Docs documents, you'll find them listed in their own sections on the same dashboard page.