The timeline is the main thing going against you.
Civil Registration only began here in 1864.
Looking at the deaths to start with.
You say that Hugh was dead by 1878.
There is only one death of that name in Galway between 1864 and 1878, and it's for 1864 ~ a Hugh King b 1804.
To be honest I don't think this is your Hugh as if they were a Connemara family then I would expect to see the death registered in Clifden.
Again, he could have died between 1861 (when Margaret was born) and 1864 when civil registration began, so you won't see a death for him OR he could have died between 1864 and 1878 and the death simply wasn't registed; this was still common for the time, even though it was a requirement by law.
Next I usually look at GV but Hugh's occupation makes this tricky.
If he was a farmer then it's quite likely he would show on the GV but it depends on the tailors situation as to whether he would or not.
Only one Hugh King shows on Galway's GV and that's one who's part responsible for paying the rents on over 100 acres; this doesn't sound like your Hugh.
Next then I look at petty session and prison records.
There are a lot for a Hugh King but I'm afraid that he was a fisherman from the Claddagh, so again not your chap.
I've looked at the census to see if the name has carried on or the occupation into possible siblings of Margaret's.
There is a Bartly King as a tailor in Market Street Clifden.
I'm not sure that this chap is worth following up on, he didn't name any of his children Hugh then again neither did Margaret.
This Bartly had a shop, and was a draper as well as a master tailor, so had some standing, this doesn't tie in with your family story of getting 'thrown out'.
So, lastly this leaves looking at the RC registers that have come online.
Salthill, Rahoon, Spiddal, Moycullen, Oughterard, Killannin, Lettermullen, Rosmuc, Ross, Kilbride, Moyrus, Roundstone, Omey, Ballinakill.
You are going to need to go through the baptisms for the churches one by one.
The first three I have listed are more towards Galway City but I have seen Connemara baptisms in them so they are worth a try as they are near to the 'border'.
Anyway, go through them one by one, I suggest trying the years 1859 to 1862.
It might seem like a big undertaking but it's your last option.
Just take your time and be patient.
Good Luck
Tara