Here are a few suggestions (none guaranteed, but it's a direction to go).
The first thing I would do is see whether there is a local (perhaps county-level) historical or genealogical society, and call them. I got a great deal of information on two of my family lines that way, as they had lots of little news clippings, etc., on events (births, marriages, deaths) that I did not find anywhere else. For instance, maybe you can find an obituary, which might mention his parents names, or his siblings, etc.
Second, I agree that contacting the church is good idea, because you just never know what records they might have. Again, they may have something mentioning his parents' names, even if in connection with his death (and if you're lucky, the whole family was in the area and all were members of this church).
With a date of death that late in the 1800s, you might also find records at a county level (but I personally would not buy books that people have compiled, as there is no form of quality control and also you have no way of knowing in advance whether what you need is in the book).
You can also post on the location and surname message boards, and see if you get a hit from someone else researching the same family.
Do you know the name of your ancestor's spouse? You might be able to track down a marriage record, which sometimes lists parents' names (and other interesting information, such as occupation, etc. - don't know about NY but that is true in some locations and for some time periods).
Do you know your ancestor's occupation? Is there any chance that he might have belonged to some professional group that has records about its members?
Now, just one little note of caution - how sure are you that the gravestone you found is your ancestor, and not someone with the same name? Do you need to check further on that point? I ask, only because a lot of names that seem unique really aren't unique at all...
Good luck with your further search - it's a puzzle, and very rewarding when you do finally find what you need.