What's the difference between stochastic and random?

A variable is random. A process is stochastic. Apart from this difference, the two words are synonyms.

There is an anecdote about the notion of stochastic processes. They say that when Khinchin wrote his seminal paper "Correlation theory for stationary stochastic processes", this did not go well with Soviet authorities. The reason is that the notion of random process used by Khinchin contradicted dialectical materialism. In diamat, all processes in nature are characterized by deterministic development, transformation etc, so the phrase "random process" itself sounded paradoxically. Therefore, Khinchin had to change the name. After some search, he came up with the term stochastic, from στοχαστικὴ τέχνη, the Greek title of Ars conjectandi. Being popularized later by Feller and Doob, this became a standard notion in English and German literature.

Funny enough, in Russian literature the term "stochastic processes" did not live for long. The 1956 Russian translation of Doob's monograph by this name was already entitled Вероятностные процессы (probabilistic processes), and now the standard name is случайный процесс (random process).

Neither word by itself has a commonly accepted formal definition in mathematics, so one cannot really ask about "the difference" between them.

They are used in phrases such as "random variable," "random walk," "stochastic process," "stochastically complete," etc, which have accepted definitions of their own. In all cases both words tend to refer to an element of chance or unpredictability. But they are generally not interchangeable; if you talk about a "stochastic walk" people will be confused.