You do have to delete the image, but you would be able to handle the redirection fairly easily. You could of course do server side redirects, but an alternative method is to use the Route Filters system.
All you need to know is the old media ID and the new media ID.
Let's say you want to redirect the photo that has a media ID of 123 to the photo that has a media ID of 124:
Admin CP > Route Filters > Create Route Filter
Find route: xengallery/{name:string}.124/
Replace with: media/{name:string}.123/
"Incoming URL conversion only" should be checked
This actually seems backwards, but it's correct. Visiting the old picture will redirect you to the new picture.