All records are sent for storage centrally to this office
http://www.groireland.ie/
This isn't in Dublin anymore - despite what many sites will tell you. The address is General Register Office, Government Offices, Convent Road, Roscommon.Tel: +353 (0) 90 6632900
Now, as you say, they will not do searches for you as they don't have the staffing levels, and their records are in hardcopy only thus far - nothing on the net. However, if you have his date of birth they'll send you copies of his birth cert, which lists his parents and crucially, their address. At this time all records were held in parish churches, and they still hold copies. Here's the difficult bit - you need to contact the church and get permission to see the records but they will happily oblige. I'm really sorry to say this, but you will need to travel to do this.
Here's where you strike gold though - your father was from Dublin, and there was a different system there... The area was divided into Dispensary districts in 1850s, and in 1864 into registrar districts. All the records you need are held on microfilm at the office listed above, and you can gain access just by phoniing ahead. But again, a personal trip is needed. Just double check before you book a flight though as these were fully accessible in the Dublin office, when the dept was decentralised that may have changed (but i don't see why it would).
Good luck...!