You don't need to use exif data. Many tools use the often ignored alpha channel of each pixel. In this case, you have X x Y bytes of available storage where X and Y are the width and height of the image.
For lossless images, you could also use the least significant bit of each color channel of each pixel to represent your binary payload. I doubt this would be noticeable, especially with a photograph.