I believe that the activation process is forwards-moving, that there is no way of "deactivating" Office so to speak - whether through uninstallation or some other process.
If you are transferring your license to another machine then you should uninstall the copy on the old machine first, as you mention. After installing Office on the new machine hopefully Internet activation should work; if not then it's just a quick five minute call to Microsoft with a simple explanation that you are moving the license to another machine.