(How) Can I use existing stapled electrical wire to fish new wire?
In my (limited) experience, it's not possible. However there may exist some experts who can do this but - of course - it all depends on the staples and wire and the situation in general. 

You could try just yanking really really hard and hoping that the staple pulls out or breaks, but when I tried this it only ruined the jacket around the old wire and the staple remained in place, blocking the new wire which could not pass through the staple because of how it was bundled to the end of the old wire. Again, there might exist a clever trick I'm not aware of that could get the new wire through the staple but it seems pretty impossible to me.

I would start thinking about alternative ways of running a wire to connect the receptacles. Are there baseboards? You could hide them in there. Is there a crawlspace above or bellow this room? If not, you just may have to do some cut some holes in the wall and repair them. 

Maybe try guessing where the staples are and cut a hole in the wall there. If you get lucky, pull out the staples. Keep doing that unill all the staples are found and removed, then use the old wire to pull the new wire through. Best case scenario, you only have two holes to repair instead of 20. Good luck!