You could start by converting the image to a polygon feature class. (Raster to Polygon)
(Maybe reclass the image to a binary raster (image = 1, nodata = nodata) first.)
This should give you a polygon of the image area: a tilted rectangle.
Run Feature Veticies To Point: this gives you corner points (plus some more, maybe)
Run Add XY Coordinates on the point class: now the points have recorded coordinates
Use a Search Cursor to find the left-most and top-most points, and grab their coordinates.
Now you want the distance between the points.
If you have ArcInfo, make a layer of the left point, and a layer of the top point,
and run Point Distance. Get the distance from the resulting table
If you DON'T: you can use trig
OR you can generate a line between the points and get the length.... whatever.
divide the distance by 4 (for your 4 x 4 grid).
In Create Fishnet:
Fishnet Origin Coordinate = the left point
Y-Axis coordinate = the top point
Cell Size Width (and Height) distance between the points divided by 4
Number of Rows (and Cols) 4
Maybe not perfect, but its a place to start...
Oh, yes, do it in Python.... Loop through the images and clean up the intermediate files as you go.