The Kelleher surname is highly concentrated in SW Ireland (Cos Cork and Co Kerry). Unfortunately, many records for these Cos haven't been transcribed yet (they're working on it). Those which are in online databases are at ROOTSIRELAND.IE (usually at a fee), and IRISHGENEALOGY.IE (free).
Using the ROOTSIRELAND.IE 20 million record database, I found it contains 9,000 Kelleher B records in all Ireland. Of these, 6,000 are in Co. Cork. I couldn't find a B record for Catherine at your DOB in Co. Cork. (NOTE - Co. Kerry records haven't been transcribed into this database. The numbers in Co. Kerry can't be determined at IRISHGENEALOGY.IE.)
Since you know Catherine's DOB was after 1863, the event MAY have been captured by the General Register Office (google GROIRELAND.IE). Catherine's parents' (Daniel and Julia Sullivan) marriage MAY also have been captured. GROIRELAND.IE's database isn't online. You will have to request a search (also at a small fee).
Ditto for James Kelleher and Julia ???? (Kelleher?).