'Deadeye' and the character 'Dead-Eye Dick'
The outlaw character known as "Dead-Eye Dick" appears to be one of the sources of deadeye in the sense of a marksman. An early mention of the character and his marksmanship appears in Arthur Holt, The Bible as a Community Book (1920):
The first person to offer a solution of the problem [of living together] was Dead-Eye Dick, the crack shot of all this district. He sought to build a community based on fear of himself. He acquired an authority which few dared to dispute. Armed to the teeth with the latest man-killing instruments, he ruled over the length and breadth of No-Man's Land.
And from "Dead Eye Dick Plays Lead in Y. M. C. A. Show," in the Rock Island [Illinois] Argus (March 9, 1920):
Dead Eye Dick and the Boys of '49 will be among the leading characters in the Y. M. C. A. circus scheduled for March 25 at the Y. M. C. A. Sidney Gordon, on of the managers of the show, says that he expects to import the most notorious sharp shooters of the wild west to help out on the circus.
Early instances where "Dead Eye Dick" refers specifically to an accurate shot include "Copettes After Dead Eye Dick: D. C. Policewomen Busy Learning How to Handle Revolver and Rifle," in the Washington [D.C.] Herald (July 3, 1919):
Although timid about pulling the trigger of the regulation six-shooter, the girls are rapidly getting in the Dead Eye Dick class, according to police officials.
The name comes up in connection with Wild West dime novels of an even earlier time, although in many of these, no special weight is given to his being a crack shot. From "Letters to Aunt Laurie From Nephews and Nieces," in the Los Angeles [California] Herald (February 14, 1909):
I had a boy friend who would read books with titles such as "Dead Eye Dick," "Indian Bill," etc., and tell me all about them, and tell stories like them when asked to give an oral composition at school. Such books as he read should never have been published.
and from "Dime Novels to Bad Man," in the [Walla Walla, Washington] Evening Statesman (January 18, 1906):
CINCINNATI [Ohio], Jan. 18.—Edward Pettis, 17 years old, consumer of "Dead-Eye Dick" novels and would-be "bad man," rushed into the office of Stem, Heidman & Mehlhope, attorneys, in the traction building yesterday, flourishing a big six-shooter. Bringing it to the level of Attorney John Rohrer's eyes, the boy ordered him to write a check for $50.
And in connection with early movie heroes, in "Moving Pictures Teach Lessons," in the Las Vegas [Nevada] Optic (November 24, 1911):
The idea is, Father Dowling said, to wean children from the melodrama stronghold that the present motion picture show typifies. There will be no Jesse James or Dead Eye Dick heroes at St. Aloysius. Comic films are in demand, however.
One early example, though, seems to use "deadeye Dick" as a personification of shooting expertise. From "Mahanoy City," in the [Shenandoah Pennsylvania] Evening Herald (April 26, 1894):
The long talked-of pigeon match between T. F. Gorman, of Mahanoy City, and Joe Martin, better known as "Deadeye Dick," also of Mahanoy City, will take place at 3:30 o'clock to-morrow afternoon, in Mahanoy Cuty, Park for $300 a side. Each man will shoot at nine birds. William Cooper, the well known marksman, is to be referee. Martin is the favorite in the betting, but Mr. Gorman is confident of winning.
And from "That Jolly Hunting Party," in the Williams [Arizona] News (November 5, 1910):
Lee Tabor, Dead Eye Dick, was first lucky, shot a 2 point buck off of the rim of the canyon and he fell 20 feet below and broke off both horns, so it was unnecessary to pack the head into camp.
The origin of the name "Dead Eye Dick" is not clearly established, but at least one person who answered to the name was a Chicago man who spent 40 years as a professional safe-cracker and robber and then became an evangelist for the next 16 years (at which point he died). A discussion of his career appears in "'Dead Eye Dick' Dies," in the Hot Springs, [South Dakota] Weekly Star (April 25, 1913), which says that Lane favored the name "Dead Eye Dick" during his years as a criminal, but gives no indication that he was particularly accurate with a gun—or indeed adept with guns at all. A photograph included in the article shows an older, bald man with heavy-lidded eyes, neither eye seems unfocused, as might be expected of a truly "dead eye." In any case, since Lane's conversion to proselytizing Christianity occurred in 1897, he was certainly known as "Dead Eye Dick" in the late 1800s, and perhaps as early as the 1850s.
Competition from and confusion with 'Dick Deadeye'
Competing with the name Dead Eye Dick is the name Dick Dead Eye, made famous in the first instance by the sailor character of that name in Gilbert & Sullivan's hugely popular H. M. S. Pinafore; or The Lass That Loved a Sailor (1878), but also appearing as the name of Wild West characters, at least as early as 1900. From "The Dirty Dozen Club," in The Dalles [Oregon] Daily Chronicle )May 12, 1896):
The club contains no bowling alley or gymnastic apparatus as yet, but the library is well stocked with such tales of adventure as "Ten Buckets of Blood, or Boy's Revenge," "Dick Dead Eye, the Blind Scout," "Nosebag Gallagher, the Terror of the Black Hills," "The Maiden's Escape, or the Keyhole in the Door," etc. Here the boys have chewed and smoked and told vulgar yarns and read hair breadth escapes, played cards and gambled to their unbounded delight for no one knows how long, but if their rendezvous is not broken up soon by the officers, the high water will do the work.
and from W.H. Morris, "A Bison Drive in Kansas," in the Salt Lake [City, Utah] Herald (October 31, 1897):
One hardened old sinner, who had knocked around the world long enough to become incredulous and skeptical to such a degree as to render himself absolutely disagreeable—a sort of "Dick Deadeye"—who had been one of the drivers that day, and who had been caught in the push, gave it as his deliberate opinion that there was nothing in this view of the case [namely that the bison drive had been a failure due to the lack of good moral character among the drivers]; that all the certificates this side of Sheol would have no restraining influence on a lot of blankety blanked stampeding buffalo.
and from "A Terror Tamed," in the Indianapolis Journal (June 17, 1903):
Dick Deadeye was a bandit bold, a bandit fierce was he, who held up stages, trains and things here in the West countree.
'Deadeye' as a noun and as a stand-alone adjective
During World War II, a U.S. infantry division acquired the nickname "the deadeyes" on account of their shooting accuracy. From Orlando Davidson, J. Carl Willems & Joseph Kahl, The Deadeyes: The Story of the 96th Infantry Division [combined snippets]:
The term "Deadeyes" came into circulation in the early years of the division but the 96th was not identified in print by that name until November, 1944, on Leyte. The division's first daily newspaper was being organized and Major Daniel W. Millsaps, Jr., its editor, received authorization from Genera;l Bradley to call it "The Deadeye Dispatch." By that time an impressive total of defunct enemy offered concrete evidence that Bradley's men knew how to handle their shooting irons and from that day on, the 96th was the Deadeye Division.
A Wikipedia article about the 96th Sustainment Brigade (formerly the 96th Infantry Division) notes that the 96th Division was created in the waning days of World War I, so it is possible, given the remark in The Deadeyes that "The term 'Deadeyes' came into circulation in the early years of the division," that the division's nickname goes back to the late 1910s or early 1920s. I haven't been able to find any source identifying the exact period when the nickname came into use, however.
The first match I've been able to find for dead-eye as a simple adjective meaning "having extremely accurate aim" is from "Charley Is in Idaho," in the Anaconda [Montana] Standard (December 2, 1892):
Out from Yellowstone and into a wild romantic region he had a dispute with a bear, which for several moments indicated a bad result with Bruin or Charley, but the result of a few dead-eye pistol shots the latter wilted and a three-mile ride to get out of beardom brought him to the camp of Ambrose Oates, to whom his experience was related in cool confidence.
Other, probably unrelated types of 'deadeye'
As bib notes in the question above, a much-earlier meaning of deadeye is a rounded block of very hard and heavy wood pierced with three holes and used as a forerunner of the pulley to take up the slack of shrouds ("one of the ropes leading usu. in pairs from a ship's mastheads to give lateral support to the masts," according to Merriam-Webster's Eleventh Collegiate Dictionary). The Eleventh Collegiate dates deadeye in this sense to 1748.
Daedeye also appears in the slang sense of "blockhead" in Herman Mellville, White-Jacket (1850, but referring to Melville's experience aboard the USS United States during 1843 and 1844):
No sooner did the bumpkin feel himself at ease, than he launched out, as usual, into tremendous laudations of whalemen; declaring that whalemen alone deserved the name of sailors. Jack stood it some time; but when Tubbs came down upon men-of-war, and particularly upon main-top-men, his sense of propriety was so outraged, that he launched into Tubbs like a forty-two pounder.
"Why, you limb of Nantucket! you train-oil man! you sea-tallow strainer! you bobber after carrion! do you pretend to vilify a man-of-war? Why, you lean rogue, you, a man-of-war is to whalemen, as a metropolis to shire-towns, and sequestered hamlets. Here's the place for life and commotion; here's the place to be gentlemanly and jolly. And what did you know, you bumpkin! before you came on board this Andrew Miller? What knew you of gun-deck, or orlop, mustering round the capstan, beating to quarters, and piping to dinner? Did you ever roll to grog on board your greasy ballyhoo of blazes? Did you ever winter at Mahon? Did you ever 'lash and carry?' Why, what are even a merchant-seaman's sorry yarns of voyages to China after tea-caddies, and voyages to the West Indies after sugar puncheons, and voyages to the Shetlands after seal-skins—what are even these yarns, you Tubbs you! to high life in a man-of-war? Why, you dead-eye! I have sailed with lords and marquises for captains; and the King of the Two Sicilies has passed me, as I here stood up at my gun. Bah! ...
Another slang meaning of deadeye is gin, according to J.S. Farmer * W.S. Henley, Slang and Its Analogues (1891):
DEADY (modern American, DEAD-EYE), subs. (old).—Gin; a special brand of full-proof spirit, also known as STARK NAKED (From Deady, a well-known gin-spinner.} [Citations from 1819 nd 1834 omitted.]
And a third meaning is evident in "Original 'Deadwood Dick' Ill" in the Bemidji [Minnesota] Daily Pioneer (March 15, 1910):
Venice, Cal[ifornia], March 15.—Richard Bullock, the original "Deadwood Dick," is seriously ill here at the home of Mayor Erskins, who was his sub-messenger twenty years ago on the bullion runs between Lead, S[outh] D[akota], and Omaha. Bullock is sixty-five years old. He has only one eye and that affliction gave him the nickname "Deadeye" before he came to own his latest sobriquet.
Although any of these other meanings may have inspired dead-eye as applied to a particular person, none seems necessary to account for the sharpshooting sense of the term.
Conclusions
Newspaper searches turn up instances of "Deadeye Dick" as the personification of a marksman as early as 1894 (although "Dead-eye Dick" as an outlaw character has a lively history without particular reference to the character's prowess with a gun), and of dead-eye as a stand-alone adjective with a similar meaning as early as 1892. These sources give no account of the origin of the term, but it seems reasonable to connect it in its sharpshooting sense to the notion of taking "dead aim" at a target, meaning, perhaps, aim that will result in the target's death. (The term dead aim goes back at least to 1835, although in that instance the aim is a direction of travel by a person, not a projectile.)
But dead as an adjective can mean a number of things besides "deadly"—including (according to the Eleventh Collegiate) unmoving (as in "dead center of a lathe"), unerring or exact (as in "dead center of a target"), irrevocable (as in "a dead loss"), complete or absolute (as in "dead silence"), and all-out (as in "a dead run"). To these we may add dead in the sense of "unaided by precision instruments," as in "dead reckoning"a term that goes back to 1613, according to the Eleventh Collegiate. For such a seemingly inert state, dead has a very lively array of meanings.