"have to see a man about a dog" (used to excuse oneself, now specif. for the purpose of using the lavatory) is on pg. 617, col. 2 of the RH HISTORICAL DICTIONARY OF AMERICAN SLANG. There is a citation from 1867.