Contextual menus were in Classic Mac OS since at least OS 8.0. If memory serves, there were also extensions (who remembers those?!) which provided them prior to 8.
I also tried to search for how much NextStep used right-click contextual menus, but that's also something that's pretty difficult to find.