Stephen Goranson found an 1885 in The Queenslander (Brisbane) of Saturday 6 June 1885 p 904:
ANGLO-QUEENSLAND FOOTBALL ASSOCIATION.
ST. ANDREWS V. RANGERS.
BY SOUTAR JOHNNIE.
Collie, taking the kick, placed the ball right in front of the goal,
while Wylie, by a nice header, put it between the uprights, and placed
goal No. 2 to the credit of the Saints.
[Trove. Australian Newspapers]
I found a possible 1887 (from "The Chicago medical journal and examiner - Volume 54 - Page 512"), but it's just shown as a snippet in Google Books so needs confirming:
In nine cases which have come under my own observation, one followed a box on the affected ear, one was due to a blow on the back of the head inflicted with the open hand; the act of diving in the sea, and the consequent rush of cold water into the affected ear, immediately preceded the head-symptoms; in two, the symptoms followed within two or three days of surgical manipulation in the ear, while in the case of the boy who was operated upon by Dr. MacEwen, the exciting cause was probably connected with his fondness for "headers" in playing at football.
This also appears to have been published in the Glasgow Medical Journal, Volume 28 (Glasgow and West of Scotland Medical Association, Royal Medico-Chirurgical Society of Glasgow, 1887). I've excavated the text further, but haven't confirmed the date, however the writer worked in Glasgow: "At the Glasgow Ear Hospital ... it has been noted by various observers, including myself...". This Glasgow journal may be easier to confirm than the Chicago one.
Also of interest, a snippet of page 44 of Scottish Football Reminiscences and Sketches by David Drummond Bone, J. Menzies & co., 1890:
Mr. Watson was a rare "header-out," and was famed for his fine tackling and neat kicking.
This can be found in full at Project Gutenberg, confirming the 1890 date.
Earlier non-football use
The football sense seems to follow on quite naturally from the OED's sense 7 ("A plunge or dive head foremost. colloq."), especially as this sense was used at schools, such as for swimming competitions: 1866, 1869, 1870 (slang definition), 1875.
It's also found applied to a certain nasty kind of cycling crash, prevalent especially during races: 1885, 2, 3, 4.