[JTE]

You need to drive one side in so the other side comes out far enough to grab with pliers. Pulling doesn't work because the domed shape expands when the force moves away from the engine.
Use a blunt tool to force the plug rather than pierce the metal.

 

[JTE]

It's easier on the inside, the goal is to get the opposite side to come outward. When installing the new ones, tap in the center while making sure it goes in evenly.

FWIW, not to sound like a know it all, but there is no such thing as a frost plug or a freeze plug designed to save your block from cracking. They are core plugs put there to empty the block of casting sand.