Hi.
At findmypast.ie the index to the parish registers is free to use and look at, but I didn't find either Eugene Brady or Margarite O'Brien's baptisms. I looked for them with a birth year of
1830 +/- 15 years. It sounds from your post like you already tried this.
Just to be clear, were Eugene Brady's mother and wife both named Margarite O'Brien, or did I read your post wrong?
Have you looked in Griffith's Valuation for Rathmines or anywhere else for Eugene or Bernard? You can search them and view them at
http://www.askaboutireland.ie/griffith-valuation/. Before that were the Tithe Applotment books (correct title?), but I don't remember offhand where they are online.
Eugene and Bernard are unusual first names, which might help. If you find them re-occurring in a Brady family in only one area of Ireland, that might be a hint.
JohnGrenham's site will let you search for two surnames on Griffiths and show where they overlapped in Ireland. You could try that, but Brady and O'Brien probably overlap in a lot of places.
And when in doubt, start Googling the names and locations. You never know what you will find.
Look for siblings of Edward Joseph Brady and find out all you can about all of them. One of their obituaries might just say something about their origins. Where did they settle? I am used to working with US records, and sometimes you can turn up a county of origin in an obituary or county history, but I don't know what UK records would reveal.
Sorry for all the usual suggestions, which you have probably run through already, but researching Irishmen gets pretty tough before the civil records start.