I checked a shipping reference book called North Atlantic Seaway which is considered to be one of the best reference sources on trans-Atlantic shipping. The only Coblenz they list was built in 1897 for North German Lloyd (Norddeutscher LLoyd). She was introduced in 1897 sailing >from Bremen to Rio de Janeiro and Santos. According to this reference source she did not sail the USA route till 1900 when she went Bremen to Baltimore and later added a stop in Philadelphia. Its possible this book is wrong but North German Lloyd was a Bremen firm so it would be very unlikely to find them in Hamburg.
Leith Line did not sail trans-Atlantic to the USA. Its possible that Leith Line had a ship with the same name but I suspect it only ran Germany to Scotland (Leith being a city just outside Edinburgh) and there your family member must have changed ships before heading to America.
Using August 1899 as a starting date look for other ships between England/Scotland and the USA with your family.
