Two more thoughts on the "idea": Start with two tabs: "included" and "excluded". All photos appear on the included tab, one big grid which is what you see at first. Provide a "remove all button" (perhaps in the menu?) which moves all photos to the "excluded" tab.
When you click on a photo on the "included" tab, that photo is moved to the "excluded" tab, and vice versa. I think that'd actually be kind of OK to work with. (There should also be a Done button, and it might be a good thing to put it in the menu/toolbar.)