There is really no evidence associating leprechauns with rainbows before the 20th century. A different answer quotes a _Time_ magazine article from 1952. 

The sole folklore-related Google Books result from the 19th century comes from _Irish Melodies_, a compendium of poems by Thomas Moore, but  a look at [the actual page](https://books.google.com/books?id=Z-ZTAAAAcAAJ&pg=PA211&dq=leprechaun+rainbow) is disappointing: the end of one poem mentions a rainbow while a footnote to the next poem mentions a leprechaun. 

What appears to have happened is a conflation of two different legends, one involving leprechauns and gold and another involving rainbows and gold. 

An 1851 book of Northern mythology talks about pots of gold at the ends of rainbows as coming from Germanic myth:

> According to a popular belief in Germany, Denmark, and England, a golden cup or hidden treasure lies where the rainbow apparently touches the ground.  This seems a remnant of the belief in Mimir's spring, in which wisdom's golden treasure was concealed. 

-- Benjamin  Thorpe, _Northern Mythology_, London, 1851, [p. 158](https://books.google.com/books?id=sIBpAAAAcAAJ&pg=PA158&dq=gold+rainbow+mimir)

Thorpe refers to Mimir's well, which lies near the Jotunheim end of the rainbow bridge Bifrost.

_The Tree of Myth_, an 1898 book of folklore by Charles de Berard Mills, states:

> Children believe at this day that a golden cup or bag of gold lied at the end of a rainbow. The story comes from the ancient sun-myth so widely diffused, of the golden orb sinking into the waters of ocean or stream or lake.  In one transformation it was the legend of a golden treasure buried in the Rhine, as we have it in the Niebelungen Lay, then finally, changed as it is in the nursery tale, we see the old myth again.

This book does not contain the word "leprechaun".

Leprechaun gold is well-hidden and guarded. It doesn't have a rainbow telling the whole world where it is:

> If you could only catch the leprechaun at his work and hold him, he would tell you where the crock of gold, his hidden treasure, lies hidden. Nor would it turn into fairy-gold, once found. But the leprechaun is artful and plays shabby trick sometimes. He was once caught by a peasan, and in return for his release indicated where a crock of gold lay. It was under a spike of ragweed in a thirty-acre field. 

 -- "[Irish Superstitions, Spells, and Charms](https://books.google.com/books?id=L6dXAAAAYAAJ&pg=PA127&dq=leprechaun++gold)",  Katherine Tynan Hickson, _The Outlook_ , collected in _Current Literature_, 1895

Notice you din't find the leprechaun's gold just lying around at the end of the rainbow, you have to kidnap the creature and make him tell you where the gold is.

This is a good segue to what appears to be what I think is the point of conflation, which is the 1947 Broadway musical _[Finian's Rainbow](https://en.wikipedia.org/wiki/Finian%27s_Rainbow)_,  by E. Y. Harburg and Burton Lane. It was a smash hit that ran for 725 performances, and was later made into a 1968 movie starring Fred Astaire and Petula Clark.
 
>Ever since I was 2, you've been seeing leprechauns and rainbows over your whiskey jug.

The play revolves around a pot of gold that Finian McLonergan stole from a leprechaun in Ireland, then brought across the Atlantic to Rainbow Valley, Missitucky. He hopes to bury it near Fort Knox in hopes ithe gold will multiply. But Og the leprechaun follows Finian to America trying to get his gold back. 

Notice it's not said the gold was found ***at*** the end of the rainbow...instead, Finian brought the gold ***to*** the end of the rainbow. Nevertheless the opening number "Look To The Rainbow" uses following  the rainbow as a metaphor for following a dream. All of the elements swirl together and it looks like that's how this entered popular folklore.