Since it is a plastic box I would grab the screw head with locking pliers ("vice grips") literally as tight as possible, and try to turn it out. This should be able to force the screw to turn in the plastic, despite the rust.
I would recommend not removing the box until you've exhausted other possibilities. The cost of the new box is not the issue, but it could take a surprising amount of effort to get a new box in there in the right position, flush, and secure. Boxes are not identical in size / shape and it obviously is fitting into masonry which was built to exactly fit the old box.
That said, if you do replace the box look for a new one that is smaller so you don't have to modify the masonry. But the box is most likely secured only by the masonry, not screws etc.
A smaller box could be initially wedged in place using shims (which can also be purchased) and then possibly just secured with generous amounts of exterior construction adhesive.
Also, since there is obviously a water issue you should try to address that. Another plastic box may be a good choice, but that doesn't eliminate the source of the water. You may be able to add some caulk and / or weatherstripping material to the outlet plate that could keep out some amount of water.
(There are outlet covers that are designed to be weathertight, but that alone doesn't prevent water from getting between the cover & the box.)