The code runs asynchronously, after all other effects of the installation have been applied. Notably, this means that your batch script won't be able to query the deleted field, because it would have already been deleted by the time your batch script starts. The only safe way to ensure that the deletion of the field won't hose things up is to not delete the field until you have run an upgrade for all customers that has an install handler that can perform the data migration (in other words, both the old field and new must simultaneously exist).
From a practical standpoint, this means you should consider any version after the deletion of fields to be a major upgrade (e.g. if the last version in a set is 2.35, then you delete a bunch of fields, the next version should be 3.0). Doing this will let you safely upgrade customers, because you can remember that the last minor version (e.g. 2.35) must be installed for clients using 2.x before 3.0, or the data migration will fail, and your data may be left in an inconsistent state. There is a reason why salesforce.com hasn't allowed this in the past, because the migration path can be messy.
As a final note, you could also skip that part and simply remember to perform a data backup beforehand, perform the upgrade, then perform a data load afterwards.