You want more details about Frank Johnson b 1843 in Norway. This link will show you an excellent forum (in addition to this one) for finding one's ancestors in Norway: http://www.norwayheritage.com/http://www.norwayheritage.com/
I'm of no direct help in your search, but I do have some ideas that might be useful in fine-tuning your approach.
I'd suggest you take a mulligan and recast your query, filling in the gaps. This is a really tough genealogical challenge and every drop of info you can squeeze out of the man's life in England will help lead to his parents in Norway. If this weren't so tough, the query wouldn't matter much. But it is (tough).
You know that he was born 1843 how? family story? You know he was born in Norway how? family story, I think you said?
His father was Oliver Johnson a labourer. You know this how?
Oliver is not a Norwegian name that I know of. Was Oliver born in Norway? Was he a Norwegian(or a Scotman on a holiay to Norway)? If Norwegian, did Oliver emigrate to England? Do you know his approximate date of birth?
What was Frank's mother's name? date and place of birth? If you don't know, which you may not!, just mention this knowledge-gap in your query, so volunteers won't think you forgot about it and they won't have to ask you.
Frank was a mariner. Source? Do you know dates sailed, places, ships, etc.?
You mention Frank's wife and family- who are they? Full names, dates of birth, places of birth, source of your info?
They started out in South Shields - ?? You mean Frank married in South Shields? Had his first child in South Shields? Where is South Shields?Full place names are always welcome.
They moved to Liverpool [England] in the 1870s. You know this how? Source? Full place name for Liverpool?
You have never found Frank on a census. "He must have been at sea on census days," - not plausible - we don't know why he's being elusive. It's really good you mentioned you searched for census records and came up empty.
He may have died in 1883 aboard a ship called Augustine, registered at Liverpool. This is according to a message posted on Gen Forum posted 2001 (you tried to contact the person who put it on but without success.) It's great that you here included a reference to the source - maybe repost the whole actual message rather than just refer to it.
I wanted to write despite my lack of Norwegian search skills because I love searches like this - and am really rooting for you to be able to move your family history back that next generation to an "old country."
IF IF IF you have an exact day month year of birth that would be a HUGE help to volunteers.