Joyhen,
John & Ann married in 1846. Here’s their marriage certificate:
https://civilrecords.irishgenealogy.ie/churchrecords/images/marriage_returns/marriages_1846/09301/5367327.pdf
They didn’t marry in Derry (as per your post). They were both living in Keady in Co Armagh (100 miles from Derry) and married there. Keady is very close to Monaghan but in a different county. Tradition was to marry in the bride’s church so that's where you might expect to find Ann’s baptism. There is a copy of Temple Presbyterian (1st Keady) records in PRONI in Belfast. Unfortunately their baptisms only start in 1838 and marriages in 1845 so sadly you may not learn too much from those records.
Alexander Moncrieff was reportedly a farmer. Most farmers would be listed in the tithe applotment records. The tithe applotment records for Northern Ireland only list 5 Moncrieff’s around 1830. None named Alexander and none in Co Armagh. None in Co Monaghan (1829) either.
Given that the couple married in Keady you would expect they came from that general area. Roger has mentioned the 2 in Derryroosk. Given that they were named Hugh & John – both names found in your family – you might want to look at them.
John Moncrieff died in Rutherglen in 1871. His death certificate indicates that both his parents were dead by 1871. His father was recorded as an agricultural labourer (not a farmer, as per the marriage cert). That may just be the informant’s best information (his son Alexander). Might not be correct. Maybe John over-promoted his father. Who knows? Cottiers were often half way between farmer and labourers. Both descriptions could be accurate. Most farmers and labourers in Ulster grew some flax (to make linen) so that doesn’t make it easier to identify any particular farmer.
Bottom line is that I think you will find it difficult to find many references to Alexander or Catherine in Irish records.
Possibly DNA testing may be a way of matching with others who have additional information about where the family originate. Family Tree DNA reportedly has more people with Ulster roots than any other company. That obviously increases the chances of finding a match. You might want to try them or, if you have already tested, you can transfer your results to them for no fee.
The North of Ireland Family History Society is running an Ulster DNA project in conjunction with FTDNA and can offer testing kits at a reduced price. http://www.nifhs.org (Go to DNA project on the website).