I'm not sure why you couldn't delete the photo as described above, by long-pressing it in the gallery and tapping the garbage can icon. You're using the Gallery app, using a 2013 Nexus 7 running KitKat 4.4.2, right? When I open the Gallery app, there are a bunch of folders. If I select the Screenshots folder, all of the saved screenshots come up. If I long-press one of them, a number of options appear at the top of the screen, including a garbage can icon. Can you confirm that you don't see that? Remember that you can only delete a photo that is stored locally on your device. If it's a photo from Google+/Picasa, you can't delete it from the Gallery app, because it's from the cloud.
Clearing the data from the Gallery app won't actually remove the screenshot picture file from your storage--it just clears the thumbnail cache that the Gallery app generates for itself when it first scans your device for media files. I suspect that at some point, it will rescan, find those photos, and repopulate the Gallery.