Ok, I've figured it out.
It is possible to apply an affine transform onto some existing CRS using FITTED_CS. Below is an example of rotation of 60 degrees counterclockwise and movement:
FITTED_CS["BPAF",
PARAM_MT["Affine",
PARAMETER["num_row", 3],
PARAMETER["num_col", 3],
PARAMETER["elt_0_0", -0.5],
PARAMETER["elt_0_1", -0.8660254037844386],
PARAMETER["elt_0_2", 1487816.0],
PARAMETER["elt_1_0", 0.8660254037844386],
PARAMETER["elt_1_1", -0.5],
PARAMETER["elt_1_2", 6886579.0]],
PROJCS["WGS84 / Google Mercator",
GEOGCS["WGS 84",
DATUM["World Geodetic System 1984",
SPHEROID["WGS 84", 6378137.0, 298.257223563, AUTHORITY["EPSG","7030"]],
AUTHORITY["EPSG","6326"]],
PRIMEM["Greenwich", 0.0, AUTHORITY["EPSG","8901"]],
UNIT["degree", 0.017453292519943295],
AXIS["Longitude", EAST],
AXIS["Latitude", NORTH],
AUTHORITY["EPSG","4326"]],
PROJECTION["Mercator_1SP"],
PARAMETER["semi_minor", 6378137.0],
PARAMETER["latitude_of_origin", 0.0],
PARAMETER["central_meridian", 0.0],
PARAMETER["scale_factor", 1.0],
PARAMETER["false_easting", 0.0],
PARAMETER["false_northing", 0.0],
UNIT["m", 1.0],
AXIS["x", EAST],
AXIS["y", NORTH],
AUTHORITY["EPSG","900913"]],
AUTHORITY["EPSG","8011113"]]
However I've found a bug in the current version of GeoTools (class cast exception when parsing this WKT). I've patched it and will also commit the fix.
I suggest to use EPSG:25832 ETRS89 / UTM zone 32N, because the Gauss-Krueger DHDN CRS zones are based on the old bessel ellipsoid, and you have to apply a datum shift that is not constant over the whole of Germany.
ETRS89 has no datum shift to EPSG:4326 WGS84 which you can get from GPS receivers, and all official cadastral information has beeen moved to ETRS89 by now.
You could set up a local transverse mercator projection on a center point of your area of interest as well, but that would gain only little improvement on accuracy against UTM.
By the way, EPSG:3857 has no real meters as units, they match only at the equator.
Best Answer
The question asks how to go about identifying coordinate systems in the future. In that spirit, rather than just providing an answer, I will lay out the thought process leading to an answer. (In general there are many more considerations than listed here, especially considerations of the shape of the graticule and its orientation. But in this case such considerations are not much help.)
At such a large scale (1:25000) near the equator (around 8 degrees north) it is very hard to tell one coordinate system from another. However, there are some clues:
The map was drawn in 2000, so it's probably a modern system.
The measurement units are clearly metric, as "hectares" and "square kilometers" attest.
Eastings range from 454,000 to about 470,000 (meters) and northings range from 9,082,000 to 9,099,500 (meters).
The inset assigns a latitude of 8 degrees 16 minutes 38 seconds and longitude of 38 degrees 40 minutes 22 seconds to a central point. This point (roughly) corresponds to the coordinates (464000, 9092000) in the middle of the map.
Annotation in the bottom right says this is a survey map. Tables in the upper left list bearings and distances. It is worth noting that projections most suitable for mapping bearings are loxodromic and most are versions of the Mercator projection.
One of the most common coordinate systems today is UTM, the Universal Transverse Mercator. It is based on a set of 60 strips, or gores, six degrees wide and extending from the equator into polar regions within each hemisphere. In the southern hemisphere the equator is the origin of the northing coordinate but is given a value of 10,000,000 (meters) to assure that all coordinates in the southern hemisphere remain positive. The origins of the easting coordinates are placed 500,000 meters west of the middle of each gore. Thus, typically, UTM coordinates in the southern hemisphere have eastings in the hundreds of thousands (of meters) and their northings are closely related to latitude, decreasing from 10,000,000 at a rate of 90 degrees of latitude per 10,000,000 meters (approximately), or about 111,000 meters per degree.
These considerations immediately suggest the coordinates are UTM. To check, we can make a conversion using (say) an online UTM converter. (Be careful! This is the fifth one I tried before I could get any reasonable results for the southern hemisphere.) The (lat, lon) of the central point converts to (463965, 9085040) in southern zone 37. We're on to something here: the easting is as close as we could hope. But the northing is about 7000 meters too low, which corresponds to 7000/10000000 * 90 = 0.063 degrees = about 4 minutes. (This uses the NAD 83 datum; NAD 27 is not applicable to this part of the world.)
This is as far as basic knowledge can take us. The result strongly indicates the coordinates are based on UTM, but one or more of the following has occurred:
There may be a small local adjustment in northings specific to this area.
There may be a typographical error in the latitude; perhaps 16 minutes should read 12 minutes? (As evidence of this possibility, other typographical errors are evident; e.g., "9097500" to the left of the upper left table really should be "9097000".)
The latitude may be correct, but should be shown near the southern tip of the inset rather than its center.
One way to check whether the coordinates really are UTM is to obtain a base layer in which some of this map's features are clearly and accurately shown; reference this map to UTM; and overlay them. If they coincide to within the errors expected of the inherent layer scales, then we can trust the coordinates are UTM. Otherwise, they are likely just a north-south shift from UTM, but further research into Tanzanian coordinate systems would be advisable, as suggested in the answer by @geographika.