I searched in Google Books for the phrase

"Sticks and stones
May break my bones,
But names will never hurt me."

The oldest examples I could find came from two books published in the same year. (I suspect they are the same text published under different titles in different countries.)

Cupples, George. Tappy's Chicks: And Other Links between Nature and Human Nature. London: Strahan & Co, 1872, page 78.

Cupples, George. Singular Creatures, and How They Were Found: Being Stories and Studies from the Domestic Zoölogy of a Scotch Parish. Boston: Lee and Shepard, 1872, page 87.

...but I suspect the proverb is much older than that.

An article called "Rhythm" by Thaddeus L. Bolton in The American Journal of Psychology in 1894 points out that it has the same metrical structure and similar alliteration to:

"Jack and Jill
Went up the hill
To fetch a pail of water."