The Ben Ish Chai (in Torah Lishmah) says that there are two reasons why we pray for someone ben his mother:
- Women have less sins (they don't have the commandment to learn Torah constantly, which is a sin that everyone violates to some degree every single day.)
- We know for a fact who is the mother, while not 100% for sure who is the father.
According to the first reason, we could say a mishebeirach after either (the 7 commandments are not time-related, and obligatory on both men and women equally). According to the second reason, even by a non-jew one should say a mishebeirach after the mother.
R' Zevin (A Treasury of Chassidic Tales) wrote that when Count Dravski went to the grave of R' Menachem Mendel of Rimanov he wrote a Pidyon Nefesh and he signed it as "Miechislav Dravski the son of Victoria".
Though hodofhod pointed out that chabad.org says a non-jew should use the father's name when writing a Pidyon Nefesh by the grave of a tzaddik.