Turn off contact syncing on the phone as your first step. Then you can delete all of the contacts from the phone without them syncing back (if you delete all of your contacts at once with sync active it will assume you did a factory reset and want them reinstalled). You can use the "export" feature (next paragraph) if you want a non-cloud backup before doing this.
From your old phone, go into the phonebook app and "export" the contacts. That will write them to a vcard file, which you copy to the new phone. Then "import" them to the phone (as Google contacts if you want to sync them later, phone contacts if you never want to sync them).
Then log on to your GMail account from a computer and remove the contacts you no longer want stored there.
Then turn on contacts sync on your phone again and it should resync them.
Note that I've not tried this whole sequence, as I've not had the desire to erase all of my contacts from the cloud. But logically I think these steps should work.
