Lindsay,
Birth registration only started in Ireland in 1864 so you won’t find a birth certificate for Annie. You might find her baptism. To do that you would need to search Belfast baptism records. You know she was Presbyterian. That’s helpful. However in the 1850s there were about 25 Presbyterian churches in Belfast. Few of their records are on-line but there are copies of most in PRONI (the public record office) in Belfast. You either need to go in person, or pay a researcher to go, to look them up. A couple of Presbyterian churches were destroyed by German bombing of Belfast n WW2, and their records are lost.
Death registration also started in 1864. I searched 1864 to 1921 for deaths in Belfast and there were only 5 Alexander Riddells. 4 of those were too young to be Annie’s father. Just one is of the right age. He died on 9th August 1866 aged 49. That certificate is pay to view on the GRONI site for £2.50. Can’t guarantee it’s Annie’s father, who might have died before 1864 when records began.
https://geni.nidirect.gov.uk/search/death
I found this probate abstract for the above death. He was evidently a merchant. Assets were under £450.:
The Will of Alexander Riddell late of Great George's-street Belfast County Antrim Reed Manufacturer deceased who died 9 August 1866 at Manchester in England was proved at Belfast by the oath of Eleanor Riddell of Great George's-street Belfast aforesaid Widow the sole Executrix.
The will itself is on-line on the PRONI wills site. No mention of any children. He left everything to his wife Eleanor Riddell nee Bell. Not sure about him dying in Manchester as his death is registered in Belfast but anyway that’s the wording on the PRONI wills site.
The 1852 Belfast street directory mentions the above Alexander. Also a second one who was a shoemaker and lived at 10 Cargill St:
https://www.lennonwylie.co.uk/1852names4.htm
He’s not in the 1861 directory so perhaps had died?
https://www.lennonwylie.co.uk/alphanames1861RtoY.htm
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 and can offer FTDNA testing kits at a reduced price. http://www.nifhs.org (Go to DNA project on the website).