I can find no single origin point for this never-uttered catchphrase, but I would hazard that it's a natural mutation of several similar phrases, the closest being a command directed at Spock instead of Scotty:
KIRK: Beam me up, Mister Spock. (From "The Squire of Gothos")
This could easily have become blurred with the various forms of this command issued to Scotty, such as
KIRK: Scotty, beam us up fast! (From "The Savage Curtain")
etc., as well as a couple instances of
KIRK: Beam us up, Scotty
coming to us by way of The Animated Series (for example, as heard in "The Infinite Vulcan").
The earliest instance of "Beam me up, Scotty" I can find in print is in Volume 79 of The Aeronautical Journal, published in 1975:
...cliffs, fire, forest or mountain is most probably some form of transporter device such as that used by Captain Kirk and the crew of the starship "Enterprise" — a sort of "beam me up Scotty" routine. However as this is still in the realms of fantasy...
(Source)
That this is the origin of the phrase is possible but highly unlikely — it almost certainly existed orally amongst the public in the late 60s during the run of TOS itself.