M-W has ca.1925. OED has 1925. The ADS-L archive has a 1912 cite. Using Newspaperarchive, _Nebraska State Journal_ 20 May, 1902, 10/3 "Peter Christiansen, who rooms at the "Rusty Shovel" on North Sixteenth street and who said he took his meals at the "Greasy Spoon," in the same locality, ...." Sam Clements