Obviously, J, the first written - or, nowadays, otherwise recorded - instance of a word or phrase's usage has to be taken as its earliest use. I'm sure we all know perfectly well that it was probably around in speech prior to that.
Perhaps, in the early 1800s, a fisherman in Kent looked anxiously across the Channel to where Napoleon was gathering an invasion force and said, "We will fight them on the beaches...we will never surrender!" and so on. However, as neither he nor anyone else wrote the words down, we're forced to conclude that Churchill originated the phraseology.