Rabbi J. David Bleich has a yutorah mp3 on this. If the parent never had a Hebrew name, there are four opinions about the child going by "son-of-[new Hebrew name]" now:
C.) Only if the parent is alive
D.) Only if the parent is dead
So he concludes the best move -- certainly for a Ketubah -- is just use the parent's English name. (And in written form, transliterate it.) He mentions that at the first wedding he actually officiated, the bride's father was "Stephen", but the family started arguing as to whether his Hebrew name was "Shlomo" or "Shmuel." In the end, Rabbi Bleich simply wrote: "bat Steven."
I realize there may be more leeway in how someone is called to the Torah than how they're identified in a legal document, but this seems to be the formal method. He also mentions a Russian Jew (two of them, actually) who signed as a witness on a Ketubah and wrote "ben Avraham"; he had a Jewish father with no Hebrew name ... "and the old men in synagogue said to call me up as Chaim ben Avraham." Rabbi Bleich told him to sign "Chaim ben Vladimir."