You're welcome Faith.
Your father's church baptismal record should have his parents names and a place of birth.
If your grandfather was naturalized citizen than yes, you should request his intent % petition as there should be some information. If he had social security numbers than the SS-5Form should have a place of birth and parents names. Do throw a wider net in the genealogy world. You might want to post on a state and a county board as well. http://www.archives.gov/research/naturalization/index.html