An article from the New York Times News Service attests *cheap shot* as appearing in print in 1971 in a football context, with unknown origins before that.

https://news.google.com/newspapers?id=mYwyAAAAIBAJ&sjid=uucFAAAAIBAJ&pg=2377%2C4227702

And rapidly making its way to political commentary soon afterwards. 
If we can trust the research of a random columnist from 1981 on the early 70's origin, it would make sense for it to grow quickly to common use, since both televised football and politics experienced a boom in that era.

The cheapness is in the sense of "deserving of contempt" (similar to the phrase "a cheap trick").