I had a very similar problem when I drowned my iPhone and switched my SIM to an old Windows Phone 7 I had lying around. If you have your old phone, you can disable iMessage while the SIM is still in it, which apparently works -- but if you don't, you're basically up a creek. I ended up changing the email address on my iCloud account.

It baffles me that online iCloud doesn't have a dashboard for controlling this. Doesn't seem it should be that hard to unlink phone numbers from iMessage.