My concern is that, even with all those precautions, someone could still embed a virus in the image. How do I prevent this from happening? Should I use a module like Image::Magick to write a new image altogether? Do I need to run a virus check on each submitted image?
Yes, and yes, and you should do both under account with limited permission. You should also remove execute permission from image file.
You should also virusscan the files periodically. A good time would be when you update virus definitions.
This is reasonably everything that you can do.