I realize that the majority of my readers are from the US or Canada, but the Irish Diaspora can be found world-wide. Keep an open mind. A relative of your ancestor may have emigrated to another location and have some part of the family history that could solve your brick wall.
England
One of the first places to look is in England. In 1851 there were 485,000 individuals that identified as having been born in Ireland and in 1861 there were 550,000. Much of this had to do with the Famine, but Irishmen had been "commuting" to England during the off season for work even before the Famine. Some of these people might never have been permanent residents of England, but only there for seasonal work. The 1841 census was done in June, however subsequent census dates were the last week of March or first week of April. Some of the workers might not have returned to Ireland yet. Also Irish serving in the military, were in the British military and might have been enumerated in England.
Why should you look in England...well, they had better records than Ireland including census records for the 1800s! Also, civil registration in England began in 1837, so if a couple married or had children in England there is likely to be a record. If your ancestors left for the US from Liverpool, they may have lived in England for a while prior to their emigration to the US. Although the census takers were not necessarily required to list the County of origin in Ireland, many did. A search for Mayo returns 7,854 individuals in 1861. Ann O'Loughlin born about 1791 in Ballymaginaghy, Down, Ireland, married Hugh Rooney (likely in Ireland before 1823) and had two children born in Liverpool, Lancashire, England about 1826 and 1830 according to the 1841 and 1851 census in England.
A search of Roman Catholic Church records for Liverpool at Ancestry turns up baptismal records for the two children shown on the 1841 census, and for a third child that was unknown. And, not surprisingly, the dates were off by a few years. The children were baptized at St. Peter's Priory and the record includes not only their baptismal date, but also their birth day, very helpful as the births were before civil registration.
I was also able to find the Probate of Hugh Rooney in 1860 in the Calendar of Wills which gave me his death date.
I could go on...at Findmypast there are 189 record sets for Liverpool, Lancashire, England between 1820 and 1880. There are also databases at both Ancestry and FamilySearch. That sure beats Ireland!
One of the questions I'm frequently asked is about records from Ireland to England. Unfortunately, there are no records of movement between Ireland and other parts of the UK. Remember, this was not a migration as they were simply moving to another part of the same country.
Scotland
The Irish also went to Scotland for seasonal work. At the closest point in Ulster, Scotland and Ireland are only 12 miles apart. Many from Ulster made that trip, sometimes for good, or possibly as a stopping off point prior to emigrating to the US or Canada from Glasgow. Civil records for Scotland began before Ireland, but after England...in 1855. The Scots collected considerably more information in civil records.
The Scotland's People Website contains Statutory (civil) records, as well as Church Registers for the Church of Scotland (this is the Presbyterian Church) from the 1500s know as the Old Parish Registers (OPR). These Registers are only for the Established or State Church of Scotland. They also have records for the Roman Catholic Church. There are some Roman Catholic records as early as 1704, but like Ireland, you'll mostly see them after the Roman Catholic Relief Acts in 1829. The category of Other church records includes any of the dissenting Presbyterian Churches, so if you're not sure which form of Presbyterianism your family followed, search both the Old Parish Registers (OPR) as well as Other.
To use the site you will have to sign up for an account, but searching is free. Once you find a record you want to view, it is a Pay-Per-View system. You purchase credits and use them to view the document. Once you've paid for a document, it remains in your Saved Images to review again at a later date. I have images saved going back to 2009. Here's an example of a marriage record from Scotland from the Scotland's People Website.
You get the location of the marriage (South Leith Parish Church according to the forms of the Church of Scotland), the names of the bride and groom, their age, address and condition (bachelor, spinster, widow, etc) but you also get the names of each of their parents including the mother's maiden name. John Sprague's father is given as William Sprig and his mother as Jane Sprig, maiden name White. Mary's parents are James Hay and Mary Hay, maiden name Hutchison. Both mothers are deceased. You also get the names of the witnesses. Neither England nor Ireland provide the mother's information.
Australia
Emigration to Australia could have been by Transportation. Between 1791 and 1867 approximately 40,000 Irish convicts were sent to Australia. The Transportation Database at the National Archives of Ireland provides an Index of convicts. It was one of the early databases and only allows a simple search. Many of these records were destroyed in the 1922 fire but you might get enough information to search in the records in Ireland, or to search newspapers for any reports on the crime or court case.
There was also a scheme to send young women from the Workhouses in Ireland to Australia between 1848-1850 . Known as the Earl Grey Scheme, (Earl Grey was the Secretary of State for the Colonies), it was designed to relieve the pressure on the workhouses throughout Ireland by sending orphans, or even those not orphaned, but whose parents could not support them, off to work in Australia.
There were also those who chose to emigrate to Australia. Passenger Lists Leaving UK 1890-1960 are helpful for later times, however there are a number of immigration indexes for those arriving in Australia from 1838-1923. I found Hugh Moughty on the Passenger List departing from London to Sydney in 1898. A random google search in 2009 turned up a notation about his service during World War I and there was a bonus!
Hugh had a sister, Mary Jane born 1873 and I had no idea what had happened to her. It was in this record that I learned she became a nun and took the additional name of her deceased sister, Gertrude; she was listed as Hugh's next of kin. I likely would not have found her had I not been looking at Australian records.
There are two more locations to discuss, but this is getting a bit long, so I'll save them for next week.
Happy Hunting and Stay Safe!