Update: Since the original question and the early answers were written, John has found out that his great-grandfather was not born in Kreuzlingen, but Sigmaringen, now in Baden-Wurttemberg in Germany. I'll leave my answer as a case study for how to find the birthplace when it is not known, since it also addresses the family story about the Swiss citizenship of the children. Some resources for research in Sigmaringen are:
FamilySearch Wiki: Germany
BYU Research Outline: Germany
Wikipedia: Sigmaringen
Sigmaringen was first documented in 1077 and was in the principality
of Hohenzollern-Sigmaringen until 1850, after which it became a
province of Prussia's Province of Hohenzollern.
FamilySearch Catalog: Germany, Preußen, Hohenzollern, Sigmaringen
There are many interesting approaches to this question.
One part of this story stands out to me:
Some of the Rebholz family story goes that my great-grandfather paid
for his many children to be given Swiss citizenship and start a new
life over the border in a neutral country with his eldest daughter who
eventually raised them (6 of them!).
Family stories often get some of the details wrong, but still hold some kernel of truth in them.
My approach would be to step back and thoroughly research this (your grandfather's) generation. With multiple people, you have many more opportunities to find records than you do for just one person. Information which is lacking about one sibling may be found on the record of another.
Collect all the records you can find about all these children. What records might have been created for them? What information about their parents might appear on those records? Since the father, and apparently the mother, will not have been the informant for many of the records that were created in the later part of their lives, it seems likely that the children will report what the eldest daughter told them, which might not be accurate. But if you find any variation in those records, treat those variations not as mistakes, but as clues.
Q1: Do naturalization records exist for the children?
What made a person a Swiss citizen in this time period? If the story is true that your great-grandfather had to go through some process to establish or re-establish Swiss citizenship for his children, what would that process have been? Behind each record group there is usually some law that was passed that dictated what records needed to be created. Have the laws about citizenship changed, and if so, when did that happen? What records would have been created? Did they survive, and if so, what archives might hold them?
Q2: Do any of the children's records state their father's birthplace? (i.e. can their records answer or narrow down the question of where Hans/Johann Rebholz was born)
Many of the records in the USA will only list a country or state for the father's birthplace, but I found the hometown of my father's (English) great-grandfather, and his place of death, on his daughter's passport application.
When people come from a small town, sometimes they will say 'I am from [small town]' and when the listener doesn't know where that is, they will give the name of the nearest bigger place. Sometimes people remember the name of the bigger place, and the real small-town origin can be forgotten. When I first started out doing my own family history, I couldn't find my father's family in the census because I was looking in the big city which was nearby. I was looking in the right county, but the wrong town. Once I talked to my brother, who remembered the small town name, I looked at the records for the small town and found the records.
Sometimes if the family moves, it is possible for people to be known as "from" the town where they grew up, but their actual birthplace will be elsewhere.
Gathering your great-grandfather's children's records may also help you find more information about his forenames.
Q3: What is the history of the Konstanz region?
Did the border change? If the same place was once held by Germany and then became part of Switzerland (or vice-versa) then that might explain someone having to re-establish their Swiss citizenship despite not having moved at all. see new section at the end of this answer, and the comment from @dirkk below
Regarding Q3: As a resident of Konstanz I can assure you the border wasn't changed in this time period. Also, the Germans did not draft Swiss citizens. – dirkk Aug 15 '14 at 19:01
Q4: What happened to their mother?
Why (and when) were the children being raised by the eldest daughter? Did the mother die in childbirth when the last child was born, or did something else happen? Who died first, the mother, or Hans/Johann? What information about the children's father might be on the mother's death record? Do probate records exist for either parent?
Q5: When did the eldest daughter reside in Switzerland?
You said "his eldest daughter who eventually raised them". When did she establish her residency in Switzerland? When did her siblings join her? What is the timeline for the entire family?
Investigating these questions, and other questions that may occur to you in the process, may yield valuable information that will help you when you take the more direct approach to the question as outlined by lejonet.
Q6: What regiment did Hans/Johann serve with?
Local histories might hold the answer to this question. Some towns produced books which recorded all the names of people who served in the war. I found a book about my husband's grandfather's town via Google Books, and a regimental roster on a website about his regiment. Once you have pinpointed the regiment, regimental histories can give you the context that will help you read any military records that might survive.
Resources
From the Family Search Wiki on Switzerland Naturalization and Citizenship linked to above:
Swiss citizenship is kept on three levels: the nation, the canton, and
the Heimatort, or home community. For most people, citizenship was
inherited, and residency was not a requirement. Thus one or more
generations of a citizen’s descendants may never even have seen their
original home community. A burger and his descendants remained
citizens of their Heimatort or Heimatgemeinde until one of them
applied for and obtained citizenship in another town.
(emphasis mine)
From Wikipedia:
Kreuzlingen is a municipality in the district of Kreuzlingen in the
canton of Thurgau in north-eastern Switzerland. It is the seat of the
district and is the second largest city of the canton, after
Frauenfeld, with a population of about 20,800. Together with the
adjoining city of Konstanz just across the border in Germany,
Kreuzlingen is part of the largest conurbation on Lake Constance with
a population of almost 120,000.
In 1874, the municipality of Egelshofen was renamed Kreuzlingen. It
reached its present size with the incorporation of Kurzrickenbach in
1927 and Emmishofen in 1928.
Could the family story have come about because your great-grandfather's children applied for citizenship in another town? Or may the extra step have been necessary because of the location of Kreuzlingen? What if your great-grandfather grew up in Kreuszlingen, on the Switzerland side, but he was actually born over the border in Konstanz?
Knowing that Konstanz is a district in Germany, not in Switzerland, and that it is not just a district, but that there is also a city by the name of Konstanz which is a twin city (that is, similar to Minneapolis and St. Paul, Minnesota in the United States, which are known as the "twin cities") to Kreuzlingen, might be an important clue in solving this part of your great-grandfather's story-puzzle. (See the Wikipedia article on Kontanz for its history with respect to the Swiss Confederacy.)
If your great-grandfather was actually born in Konstanz, that might explain why he was called on to fight in the German Army. Did Germany try to draft German-speaking citizens of Kreuszlingen?
I do think it might be productive to ask Kreuszlingen for records about your great-grandfather, but rather than simply asking for a birth record, it might be more productive to say that you aren't sure which of the two cities he might have come from, and to ask what records (of any kind) are available for your search, so you understand what specific record collections you can ask them to search. See the question: How can I determine what records are available in a particular locale?
