Green’s Dictionary of Slang

(orig. Aus./N.Z.; later US) to dismiss someone from a job, as a lover etc.

1936		H.B. Gilmour cartoon in Truth (Wellington) in Grant Unauthorised Version (1980) 136: The Hon. R. Semple has told the country that members of Government boards who obstruct the Government will [...] be given ‘running shoes.’ [DNZE].
1941		Baker N.Z. Sl. 53: To give a person his running shoes, to dismiss a person from office (also a political use), which is an extension of the phrase to get the run.
1955		B.J. Cameron Collection (TS July) n.p.: running shoes, give someone his running shoes (v) To dismiss from an office or job [DNZE].
1963		W.H. Pearson Coal Flat 111: Like Bob Semple used to say about hit-and-run drivers-give them their running shoes.
1988		McGill Dict. of Kiwi Sl. 50/1: give somebody their running shoes dismiss from political office.
2003		McGill Reed Dict. of N.Z. Sl. [as cit. 1988].