Modeling clay, not molding clay. I do not know, but I believe it is water based because it will dry out if left exposed to air for too long. I keep my box in a zip lock bag. I think I bought it at Hobby Lobby or Michaels.
If the solder is mostly melting, then you just need more time with the heat gun (but don't melt the plastic). That's what the dental pick is for. If you find that some pins are lose while others are still held in place, then you need to apply the heat gun to the hardened areas more, but continue sweeping it across the connector--just give it more duration over the unmelted area.
It sounds like you were almost there.