Not sure what the real question is...
PD software -- You do not really need to uninstall Parallels - it will not "liberate" your license anyway. Download demo of the Parallels version you had, install on new computer and license with your key. If you get dreaded message that you cannot use it (too many activations?), you need to submit help request to Parallels and explain them situation. They should enable another activation.
VM data -- If you are asking about moving your data & VM machine, then this should be really easy, more or less automatic, process. Migrate Mac data from TM on new computer and copy the latest version of VM you have. If you are doing routine backups you should have TM with Mac data + copy of VM on external media so this is as simple as connect by USB to new Mac and go...
If you do not have data and VM in backup, you need to get the drive out from dead Air and install it in some kind of case where it will work. This may be challenge as Airs do have unusual drives, I believe. You need dock or something similar which would take the Air drive and connected it to USB.
