According to the book Brave New Words: The Oxford Dictionary of Science Fiction (by Jeff Prucher)*, the term alien referring to extraterrestrial beings goes back as far as 1820. However, the earliest usage appears to be figurative. Here is the definition and the first usage:
alien n. an (intelligent) being from a location in the universe other than one’s own, especially one not from the earth. Also used fig. Compare SPACE PERSON 1, STARMAN 1, STAR-PERSON.
[1820 T. Carlyle Collected Letters of Thomas Carlyle & Jane Welsh Carlyle Vol. 1 286: I am like a being thrown from another planet on this dark terrestrial ball, an alien, a pilgrim among its possessors.]
Below are the other terms related to alien and their first usage from the same book:
The adjective alien referring to an extraterrestrial place goes back to 1919 but there is a figurative usage from 1913 under the fourth sense below:
alien adj. 1. other than one’s homeworld; of another planet or place in the universe.
1919 A. Merritt Moon Pool (1994) 355: Flashing out, and this only when the—face—bore its most human resemblance, into twin stars large almost as the crown of little moons; and with that same baffling suggestion of peep-holes into a world untrodden, alien, perilous to man!
2. unlike anything that could have originated on the Earth.
1929 J. Williamson Sci. Wonder Stories (Aug.) 243/1: I felt far more of it than I saw—a will, a cold and alien intellect, a being, malefic, inhuman, inscrutable. It was a thing that belonged, not in the present earth, but in the tomb of the unthinkable past, or beyond the wastes of inter- stellar space, amid the inconceivably [sic ] horrors of unknown spheres.
3. of an alien or aliens.
1934 P. Barshofsky One Prehistoric Night Wonder Stories (Nov.) 697/1: Tirelessly, the alien horde labored on, struggled to make this planet, yet in its infancy, theirs.
4. that originated on another planet or place in the universe or that was made by the inhabitants thereof.
[1913 A. Meynell Christ in Universe Poems 115: But in the eternities, Doubtless we shall compare together, hear A million alien Gospels, in what guise He trod the Pleiades, the Lyre, the Bear.]
Space alien is from 1954:
space alien an alien specifically not from the earth. [This phrase is often associated with reports of or stories about UFOs and abduction by aliens.]
1954 Fantastic Universe (May) 134: Cinema-makers are now trying to avoid further boycotts by using space aliens for villains.
Alien life from is from 1931:
alien life form a creature from another planet or place in the universe.
[1931 E. E. Smith Amazing Stories (Sept.) 557/1: I have thought of it at length. It is disgusting. Compelled to traffic with an alien form of life!]
Extraterrestrial referring to an alien is from 1941:
extraterrestrial n. [< S.E. extraterrestrial, adj., “coming from outside the Earth”) an ALIEN.
1941 [S. D. Gottesman] Cosmic Stories (July) 15/2: Should a half-breed with the abnormally long hands and black teeth of a Betelgeusian pass the marines, there would be bloodshed and no questions asked. After a few hours of the reign of terror, the extraterrestrials crept into cellars and stayed there for the duration.
Non-terrestrial is from 1932:
non-terrestrial adj. not from the planet Earth; extraterrestrial.
1932 C. A. Smith Testament of Athammaus in Weird Tales (Oct.) 515/2: My scientific turn of mind [ ... ] led me to seek an explanation of the problem in the non-terrestrial side of Knygathin Zhaum’s ancestry. I felt sure that the forces of alien biology, the properties of a trans-stellar life-substance, were somehow involved.
Starman is from 1932:
Starman n. 1. an ALIEN. Compare SPACE PERSON 1, STAR-PERSON.
1932 R. Gallun (title) Wonder Stories Quarterly (Winter) 222: The Revolt of the Star Men.
Star-person is from 1932:
star-person n. an ALIEN. Usually pl. Compare SPACE PERSON, STARMAN 1.
1932 R. Gallun Revolt of Star Men in Wonder Stories Quarterly (Winter) 240/1: It was the space nausea which had made early interplanetary travel such a nightmare. The Star People, — born where gravity is almost unknown, were of | course not affected in the least.
Space person is from 1952:
space person n. 1. an ALIEN. Usually pl. — Compare STARMAN 1, STAR-PERSON.
1952 O. Lebeck & A. McWilliams Twin Earths in Post-Standard (Syracuse, New York) (July 8) 15: Ladies and gentlemen, in a few seconds you will see live specimens of the strange space people who attacked and conquered Terra!!
Bug-eyed monster is from 1939:
bug-eyed monster n. an alien, especially one portrayed stereotypically. Also used fig.
1939 M. Alger Thrilling Wonder Stories (letter) (Aug.) 121/2: Speaking of The SPWSSTFM, the cover inspired me to organize the SFTPOBEMOTCOSFP (Society For The Prevention Of Bug-Eyed Monsters On The Covers Of Science- Fiction Publications.)
Note: Per Wikipedia and the cited source Plagues, Apocalypses and Bug-Eyed Monsters (By Heather Urbanski):
The bug-eyed monster (BEM) is an early convention of the science fiction genre. Extraterrestrials in science fiction of the 1930s were often described (or pictured on covers of pulp magazines) as grotesque creatures with huge, oversized or compound eyes and a lust for women, blood or general destruction.
There are other terms that appear in later works like humanoid, insectoid, nonhumanoid, galactic, eetee etc.
Additionally, there are terms like Martian, Jupiterian, Jovian, Lunarian, Mercurian, Neptunian, Plutonian, Saturnian, Solarian, Uranian, Venerian, Venusian for the imagined inhabitants of other planets and celestial bodies. (as you mentioned some of them in the question)
Mercurian is from 1698 and appears to be the earliest term:
1698 trans. C. Huygens Celestial Worlds Discover'd 106: There's reason to doubt, whether the Mercurians [L. Hermopolitae]..are much more airy and ingenious than we.
Lunarian is from 1708:
1708 British Apollo (No. 13) 2/2: Be those Lunarians false or true.
Saturnian is from 1738:
1738 Gentleman's Mag. (Vol. VIII) 315/2: Some cold Saturnian, when the lifted tube Shows to his wond'ring eye our pensile globe, Pities our thirsty soil, and sultry air.
Uranian is from 1834:
1834 J. Chickering in J. V. C. Smith Sci. Tracts & Family Lyceum II. 137 On the contrary, the Saturnians or Uranians must have superior acuteness of vision.
Neptunian is from 1870:
1870 R. A. Proctor Other Worlds than Ours 173: The Neptunians would be wholly unable to See Uranus.
Jovian is from 1871:
1871 R. P Smith Sci. & Revelation in Modern Scepticism (1871) 155: Let us suppose ourselves philosophers come, we will say, from the planet Jupiter, on a mission intrusted to us by the Jovians, to examine and report upon the nature of the creatures which people the four inferior planets, Terra, Venus, Mercury, and Mars.
Martian, Venusian and Venerian are from 1874:
1874 The Galaxy (Jan.) 127/1: The Martians would therefore be in a better position for understanding our attempts at opening up communication than the Venerians.
1874 A. Blair Annals of 29th Century 56: I suspected from the circumstances the frames of the Venusians were so constituted that sustenance was superfluous.
Solarian is from 1930 (the obsolete sense) and 1942 (the usual/current sense):
n. 1. Obs. an inhabitant of the Earth’s solar system.
1930 J.W. Campbell Black Star Passes in Amazing Stories Quarterly (Fall) 521/2: The Solarian one-man ships were even smaller than the Nigrian one-man ships, and some of these did a tremendous amount of damage.
n. 2. an inhabitant of Sol.
1942 [H. Clement] Proof in Astounding S-F (June) 103/1: A record was made, and the Solarian resumed.
Plutonian is from 1931:
1931 S. H. Coblentz Into Plutonian Depths in Wonder Stories Quarterly (Spring) 323/2: Not less than eight or ten distinguished-looking Plutonians had been summoned for the occasion.
Jupiterian is from 1941:
1941 Cosmic Stories (Mar.): Please use literate terminology for the names of planet dwellers. Let’s have no Mercutians, Venutians, Plutians, Jupiterians or Terrestrials running around.