The only thing I can suggest is trying the Irish History Foundation for a birth record. You must have a good estimate for his birth year. Kelly's are numerous and John was the most used name in Ireland so you will likely be
given several choices. Baptisms usually comes with mother and father's names, mother's maiden name, date and parish/place. Most of their RC records start 1810+ so hopefully you will find the right one.
Current phone book shows 235 Kelly's.
Griffith Valuation 1849:
1,287 Kelly's, 145 named James (which should be John's father and William being Anne's father) There are 190 named John Kelly.
Tithe Applotments: www.genealogy.nationalarchives.ie