The word is known at least since the 1400's, but did not come to mean 'rubbish' until the 17th Century (OED). For another harmless food word which acquired a bad meaning, see Cheat.
Original Receipt in the 15th Century 'Austin Manuscripts' (Austin 1440)Garbage. Take faire garbage, chikenes hedes, ffete, lyvers, and gysers, and wass them clean; caste them into a faire pot, and caste fresh broth of beef, powder of peper, cane, clowes, maces, parcely and sauge myced small; then take bread, stepe it in the same broth, drawe it through a streynour, cast thereto, and let boil ynowe; caste there-to powder ginger, vergeous, salt, and a little safferon, and serve it forthe.
[Take good-quality innards, chicken's heads, feet, livers, and gullets, and wash them clean. Put them in a clean pot and add fresh beef broth, ground pepper, cinnamon, cloves, mace, parsley and sage chopped small. Then take bread, soak it in the broth, force it through a strainer and add it back to the broth, and let it boil well. Add powdered ginger, verjuice, salt and a little saffron, and serve it.]