TV Tropes has a few pages devoted to this trope (warning: TV tropes links):
In a sexy discretion shot, the couple is starting to get intimate when the camera pans away in a very obvious way. Or the scene fades out, and the next scene makes it clear that something has happened in the meantime. A "something else also rises" shot is similar, but the shot may specifically switch to something reminiscent of the act or the body parts involved in the act (like the chimney rising and falling during the Python skit).
These kinds of shots probably go back to the beginning of the movie-making industry. Certainly, the introduction of the Hays Code during the 1920s and 1930s created a need for directors to come up with creative ways to tell their stories. Discretion shots are a way to say "and then these characters had sex" without running afoul of the censors.
I’m asking for the origin of stock footage being used as an innuendo.
This is a bit of a misapprehension. The Python skit used stock footage because--aside from the fact they probably had no budget--the stock footage enhances the joke. Discretion shots were already a cliche by that time, mostly associated with older, mostly black & white films. Using blatant, old-timey imagery make the joke more obvious. And it leads to the skit's punchline, in which the man is actually showing old films.
If you see a discretion shot using blatant stock footage and cliched imagery, it's probably because it's a joke or parody of the idea of discretion shots--like the Python skit. When a film wants to include a discretion shot for real, the director is going to try to do something new and clever with it, so each case will be unique in some way. If the director chooses to use a visual euphemism, the production can film its own footage, or at least use stock footage that isn't so obvious.
Most of the films discussed on the tvtropes pages are newer than the Python skit (the skit itself is mentioned on the sexy discretion shot page). But a few of the entries are about older films.
This one is from Swing Time (1936). It doesn't involve a cutaway, but it illustrates that the idea of a discretion shot dates to the early 30's at least:
This one is from To Catch a Thief (1955). It uses repeated cutaways to a visual euphemism which gets more obvious as the scene progresses:
This scene is from the end of North by Northwest (1959). It specifically uses imagery of a train entering a tunnel: