Put a long lever in the shoe, like a 3 ft plastic pipe, and just twist it off. The cleats don't have a handedness, and the right vs. left shoe is irrelevant (unless your feet are in them). It is also impossible to put them in backwards.
Just twist it off.
When you get them off, set the tension screws on the pedals to their lowest settings, put your feet in the shoe of the correct chirality, and try again.