I hadn't noticed you post his birthyear previously and without that any search would be nearly impossible. Too bad he was a couple years too late to be captured in the 1865 census.
You could also obtain some fair estimate of what year that he emigrated from Norway from the 1900 US federal census. That information would allow some idea of where in the emigration from Norway records a possible lead might be found.
Church records in the congregations where he might have been a member after emigration may have noted what parish/parishes he was originally baptised in and perhaps even the name of his father and/or parents.