1. Change your foreground color chip to the color that you wish to use for the new background
2. Duplicate the background layer, then shut off the visibility of the background layer by clicking on the eye icon. Work on the Background copy layer
3. Use one of the selection tools, e.g. magnetic lasso tool, lasso tool, or selection brush, to select the foreground. This has to be done precisely, or you will have stray pixels remaining, as you have experienced . When using the magnetic lasso tool, be sure that the feather value is 0 (zero)
4. Once this step is complete, go to Select>inverse and hit the delete key on the keyboard
5.Press CTRL+D to get rid of the selection outline ("marching ants")
6. Use the eraser tool to tidy up if you see any stray pixels. The checkerboard pattern denotes transparency
7. Activate the Paintbucket tool and left click once over the transparent area for the new background.
8. This is a manual process and there is no provision for a batch process that I am aware of.