If you have access to the record on him from the 1900 Census, you can check and see whether he was himself born in the US or which year he emigrated to the US. If he was the immigrant, then you can take that year (and give yourself +/- 2 years), then you can go to a large library that has a copy of the series called Germans to America. That will give all of the passengers who the researchers believed to be of German heritage, and the date of their emigration. Armed with that, you'll have the port where they departed and can then write to the German Bundes Archives to see if there's a copy of his passport/visa available. That would be the only official document that someone emigrating in the 1800s would have filled out disclosing the town of his birth.
As for land records, they may or not be a help, but if you go to the Bay Co Registrar of Deeds website, you can search for him. I'm not sure that there's a complete file all the way back that far, so if it's not then you'd have to visit the Registrar's office on the 1st floor of the County Building and go through a room full of huge old musky ledgers to see if you can find any records on him.