Hello Nelson,
Hopefully another can supply some information. It appears some information has been handed down through the years. Maybe gathering info beginning with the GGf & working backward, as his birth records. Quite honestly, I hardly know where you can start, unless Brazil has immigration records that you can access, & employment records, wills, tax & church records. One usually gathers everything there is to be had in the receiving country prior to going back to original country. there is likely info on net as to routes from one country to another. They may have come with friends,& all worked and lived close to one another, thus tracking another's route may help.
There are so many ports within Europe in different countries. I've never had any success with the Hamburg records on-line, & Bremen is only available in bits and pieces; however, you may be luckier than I was. And then they may have arrived via indirect routes as Europe to North Africa and on to Brazil. Possibly there are clues in obituaries and maybe (I don't know what Brazil has) newspaper accounts, census reports, death certs. You could query Ancestry.com or other genealogy companies for information on Europe to Brazil. LDS has likely filmed records in Brazil. Is it possible they first came to US and later on to Brazil? If so, getting them from Germany to US wouldn't be as difficult. No idea of from US to Brazil.
Wishing you much success. I was blessed finding second cousins who held more info than I had. I am assuming you are on Rootsweb surname list for Koch. and you may want to start one for German immigration to Brazil.
Jane