You can't change an account's name. That sucks when you buy one, but that comes in handy when you need to retrieve one.
Just make up something like : "I got my account hacked a while ago and out of spite I just left WoW. Now I'd like to get back to it and I would like to know if there's a way to get my account back."
With any luck they will ask for a scan / photo of an ID + today's paper. Since your legit, it should be fine. Back in the days you could also provide the original CD key as a second means of verification.
Also, contact them via a ticket on their support site (
https://eu.battle.net/support/en/ticket/submit or
https://us.battle.net/support/en/ticket/submit), not by phone (since the phone support actually just throws a ticket at the actual one).