Don' t look to the name. Try to collect other puzzlepieces together. Ask around all people who knowed him and speaked with him in reality.
Did he ever tell that Samuel was not his real callen name? Did he tell that he was callen at home (from mother, grandma, siblings) by another name? Or did he tell about more first names?
What was his konfession? Jewish? Greek Catholic? Roman Catholic? Protestant? Did he change it? What church did he visit?
Search for the birth-certificates of each child in the churchbooks, not in the civil-record. If possible order a photocopie, no copy, cause sometimes pastors note where someone was baptized (hope they do this also in USA ;-)) Also marriage-certificate from church-records.
Try to get every original certificate were Samuel Katz had to note his name officially.
What languages did he speak? What was his mother tongue?
What nationality did he has, as he told from himself? Polish? German? Ukrainan? Russia? Austria at that time was a mixture of different nations. It would be helpful to know to which group he belongs, cause than its (a little bit) easier to find the birth name.
What was the reason of immigration? Why does he leave his home? Thats such a decision - people have a very good reason to do that. To know his reason can be helpful.
Did he immigrate alone or is known about other Immigrations? Friends? Related?
If you can tell us more about that, maybe we will find out more.