J.E. Lighter, The Random House Historical Dictionary of American Slang (1997) reports that "hand job" in its sexual sense goes back to 1937:
hand job n 1. an act of masturbation, usu. by one person on another who is a male.—usu. considered vulgar.
[First citation:] 1937 [Pietro] Di Donato Christ in Concrete 107: Then ... go into the cellar and do the hand-job!!!
2. an act of insincere assuaging or assuring; flattery; blandishment. [First cited references is from 1972.]
The first Google Books match for the term as used in definition 1 above is from Theodore Rubin, In the Life (1961), a nonfiction book on prostitution, which includes the following glossary entry:
hand job: stimulation of the genitals using the hand.
However, "hand job" in this sense appears not to have been a widely understood term outside the demimonde of prostitution until the late 1960s, as evidenced by continued (and fairly frequent) innocent use throughout the 1960s of "hand job" to mean a non-mechanized task. For example, from American Egg and Poultry Review, volume 23 (1961) [combined snippets]:
...the boning process, being a hand job, could not increase poundage except by a slow costly increase in man power which required also increases in floor space, tables, pans and other equipment. The Harris machine, by using the same labor, can increase the volume per man hour of meat boned by 50%. It streamlines and compresses the whole boning operation in a space half the area used by the previous hand boning method.
From U.S. Government Printing Office, "Theory and Practice of Bookbinding," issue 1 (1963) [combined snippets]:
Frequently it is necessary to preserve a group of plates or sheets that do not lend themselves readily to binding and boxes are made for this purpose. Slip cases to be used for the protection of fine binding and books of great value are also made. Map mounting is another miscellaneous hand job performed by the bookbinder.
From Railway Track and Structures: RT & S, volume 64 (1968) [combined snippets]:
The other alternative is to resort to a hand job, removing as much old ballast at ends of ties as possible to leave a crown in middle of track. Blocking should then be inserted at the ends of the ties for support while the remainder of old ballast is removed and moved out by push cars to dump at the ends of the bridge.
And from William Craig & James Collins, New Vistas for Competitive Employment of Deaf Persons (1970) [combined snippets]:
“Variable Machines”. The make of machine, tool, or equipment by which a task is performed may be significant. For example, printing machine - a small hand job press versus a large automatic press.
The breakthrough in U.S. public consciousness of the sexual connotation of the term may have been Philip Roth's use of it (multiple times) in Portnoy's Complaint (1969). It seems highly unlikely that the term was in use in Deadwood, South Dakota, in the era of Wild Bill Hickok (who died in 1876).