I just went through this.
I found that (it appears anyway) that as long as the product has not yet been activated, if you do Change... for Microsoft Office 2013 in Control Panel > Programs and Features, and then do an Online Repair, an option is presented for changing the product key.
It was just a small link underneath a button that I think said "No thanks, just change the product key" or just "Change the product key," I can't remember for sure.
Anyway, it worked. It took quite a while for the install to finish (about 30-35 minutes I'd guess), but it is all working. I then had to activate over the phone because this copy of software had been used on another computer accidentally and then was uninstalled,
but other than that everything seems to be running perfect.
Hope this helps.
Thanks. Worked for me. Just went into Control Panel --> Programs and Features --> Right click MSO 2013 --> Change --> Last option says "Change your product key" --> Entered new key --> Ready to use in 5 mins !
Thanks again ! :)
Edit: Had to activate once (did the Internet activation).