A “mother-in-law sandwich”—yet another mother-in-law joke—usually contains the jocular ingredients of “tongue on rye” or “cold shoulder and tongue.’ The sandwich has been cited in print since at least 1936 and 1957.
 
Unlike a “ham sandwich” and a “turkey sandwich,” a “mother-in-law sandwich” does not contain a mother-in-law.
 
 
28 September 1931, Cleveland (OH) Plain Dealer, “Feminine Vocabulary Has Some Special Definitions Women Alone Understand” by Dorothy Dix, pg. 18, col. 7:
Mother-in-law—A hereditary foe.
Husband’s Friend—A bride’s danger. One to whom you serve cold shoulder and pickled tongue.
 
27 February 1936, Pomeroy (IA) Herald, “Here and There” by Mrs. I. E. C., pg. 1, col. 6:
“What will you have to eat?”
“Oh, give mo a mother-in-law sandwich.”
“What’s that?”
“Tongue.”
 
29 August 1957, Greensboro (NC) Daily News, “Today’s Chuckle,” pg. 1, col. 3:
A local eating house features a mother-in-law sandwich—cold shoulder and pickled tongue.
 
Google Books
Handbook of Humor for All Occasions
By Jacob Morton Braude
London: Bailey Bros. & Swinfen
1958
Pg. 308:
Mother-in-law sandwich: cold shoulder and tongue.
 
Google News Archive
8 July 1959, Pittsburgh (PA) Post-Gazette, “Letters from Mamma” by Cliff Arquette, pg. 2, col. 2:
I just made your father’s lunch—a mother-in-law sandwich. Cold shoulder and tongue.
 
March 1960, Fast Food, “Fountain Service” by Harry Press, pg. 40, col. 1:
I entered pharmacy about 39 years ago.  The first store I worked in had a soda fountain, and I fell in love with that end of the business.
 
In those days, soda fountain workers had a language all their own.  In order to save (Col. 2—ed.) time, or just to be different, they used abbreviations or code words, or numbers for almost everything they ordered.
   
Some of these were quite clever, but some were often embarrassing to the customers.  For this reason, most chain (Col. 3—ed.) stores and a great many independents have stopped using them.
   
Here are a few of the “codes” still used behind some fountains.
(...)
Mother-in-law—tongue on rye.
 
6 November 1960, Cedar Rapids (IA) Gazette, Parade magazine, pg. 16, col. 2:
Here’s what they mean when they say
BURN THE BRITISH
(...)
Mother-in-law…Tongue on rye
 
29 April 1964, Springfield (MA) Union, pg. 2, col. 6 ad:
P.S. Duncan discovered an exciting new"Mother in Law” sandwich, Cold shoulder and lots of tongue, only available on Feb. 29th.
(“21” Lounge.—ed.)
   
Google News Archive
18 October 1976, Milwaukee (WI) Sentinel, Alex Thien column, pt. 3, pg. 1, col. 1:
OF COURSE, YOU heard about the delicatessen offering the mother-in-law sandwich — cold shoulder and lots of tongue.
   
Google Books
Bob Logan’s Tales from Chicago Sports:
Cubs, Bulls, Bears, and Other Animals
By Bob Logan
New York, NY: Skyhorse Publishing
2012
Pg. ?:
“Tired of the burnt coffee your insignificant other recycles for breakfast, along with her special mother-in-law sandwich—cold shoulder and tongue?”