This is what I've done before, definitely time consuming, not a fast operation.
Depending what type of headers are used (sounds like male headers?), I would carefully remove the plastic separator of the headers, then snip away each pin, taking care not to pull/damage the plated header holes.
Once the Moteino is detached from the other PCB, use the soldering iron with some added solder if needed to remove all the cut header pins from the Moteino (and other board if needed).
Finally clean the Moteino header holes with solder sucker.
I would not recommend hot air at all, it will delaminate the PCB layers, causing all kinds of invisible damage: broken vias, damaged parts that may not fail immediately (ceramic especially may still work but at a very different value than specified).