What is the origin of the “double entendre” stock footage trope?

TV Tropes has a few pages devoted to this trope (warning: TV tropes links):

• Discretion Shot -- Category for shots which imply something rather than showing it
• Sexy Discretion Shot -- Discretion shots about sex
• Something Else Also Rises -- Shots with a visual euphemism for sex

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:

The trick used is the music connecting the two cuts suggesting the stock footage to be a metaphor of what is happening. The stock footage is perceived as a metaphor because sex scenes have been generally censored on screen since the invention of the television.

I’m sure this is a parody of something - is it a specific movie? Or a general trope from movies at the time?

The stock footage being used is not a parody of an other film. But Monty Python is parodying (perhaps German) porn films and its background music of that time.

What was the first movie to use this technique?

The technique used is not specifically limited to stock footage. It is a story within a story. Or you could say a film within a film. The joke worked will because the audience thinks there is only one frame, and it later turns out to be a frame within the mise-en-scene.

I cannot pinpoint the first movie to do so as this was a result of

Production Code / Hayes Code

So in the 1930 when the Motion Picture Producers and Distributors of America, under Hayes presidency, adopted the rules, the MPPDA was the institution that allowed distribution of movies in USA (as most cinemas were studio owned).
Movies that were already made, or in production, needed to adopt to the new rules. This result in the need of cutting out the "sensitive" parts.
So why not just cut it out and just make the movie shorter? Because studios owned cinemas but in the "franchise" type of a deal. So they needed to provide content for a cinema to run for a whole working day. If they cut movies shorter the cinema director could fill the time with other (older) movies (where the cut for studio was paid for), additional ads that didn't produce revenue for studio or just work shorter which of course mean lower confection selling.

And of course, people like to get as much as possible for their money so they could boycott studios that make shorts and charge a full price.