Now we’ve all seen the trend for high contrast blue orange grading of movies. But when was the lightning scheme first brought in for shooting general night time scenes rather than using blue filters or minimal arc lights? This doesn’t have to be through digital grading as I’ve seen other comments noting that Blade-runner implemented the scheme and I imagine that dialogue round a camp would be an obvious one.
First things first, "night scenes" and "teal and orange" are two different things. One is a technique and the other one is a color grading method.
Some extra trivia: In USA the technique is called "day for night". In Europe it's called "American night" (nuit américaine).
I can't pinpoint it to a certain movie (but many critics point to Wizard of Oz*) or date but it happened with colorization of black and white movies. In those B&W ones the night feel was made by tinting the film itself with indigo or by brightness/contrast. So to work on those materials required moving white to orange which changed blue(-ish) to teal.
In "ye old day" operators used blue filters on cameras so it saved time in post processing (imagine working on every single frame in a 2 hour movie). Why is it present in modern movies? Because people. People have this nasty habit of being orange (Hello Donald). And because we live in the digital age our movies are corrected usually by some algorithm. And if you don't go there and manually tweak some changes or set a color scheme (like in Amelia) it will ALWAYS complement people (present in almost all scenes) with teal.
You mentioned Blade Runner and you would be right BUT it's mostly present in the Final Cut. Which was released in 2007, and you may guess, with computer color grading.
* As a moment of treating film (celluloid) in such a way that the colors are compliant with each other and sepia (orange) moments harmonize with color scenes.