Let me open with a quote from Hofstadter's classic Godel-Escher-Bach:"In my opinion, if one is interested in understanding Gödel's proof in a deep way, then one must recognize that the proof, in its essence, consists of a fusion of these two main ideas. Each of them alone is a master stroke; to put them together took an act of genius. If I were to choose, however, which of the two key ideas is deeper, I would unhesitatingly pick the first one-the idea of Godel-numbering, for that idea is related to the whole notion of what meaning and reference are, in symbol-manipulating systems. This is an idea which goes far beyond the confines of mathematical logic, whereas the Cantor trick, rich though it is in mathematical consequences, has little if any relation to issues in real life". The Gödel numbering gets us a predicate Prov(x,y), which obtains when x is the Gödel number of a proof whose conclusion has Gödel number y. The Cantor's diagonal argument, non-trivially converted by Gödel into a fixed point theorem, gets us a sentence G with Gödel number n, provably equivalent to ∀x¬Prov(x,n). This is the Gödel sentence, and it is provably equivalent to the one "saying" that it is unprovable.
Gödel's insights are his own, his closest precursors weren't too close. What was "in the air" by the end of 1920s is that formal mathematics probably can not prove its own consistency, like Hilbert wanted, but not a particular path to it. And it was the air breathed by select few (Skolem, von Neumann), even Russell, Wittgenstein and Zermelo did not belong to the club. When Gödel's proof came out they were surprised by it and apparently mistook it for a paradox, like Russell's in Frege's original logic, see What sources discuss Russell's response to Gödel's incompleteness theorems?
The idea that symbols are just like numbers, and manipulating them is just like doing arithmetic, was Hilbert's, it was the basis of his formalist programme of mathematical foundations. At the time the prevailing wisdom was that while Kant was mistaken about the a priori nature of geometry he was right about arithmetic (although Hilbert and Frege disagreed whether it was a priori synthetic like geometry or a priori analytic like logic). Hilbert's innovation was to analogize arithmetic to formal deductions in axiomatic theories, and conceive of that as the ultimate basis for all of mathematics. Mathematics as a priori reasoning about symbols according to formal rules, see Is there a Kantian influence on Hilbert's formalist programme? It is a supreme irony that the very idea that drove Hilbert's programme carried the seed of its demise. But Hilbert thought of it as extension, it did not occur to him to literally code meta-mathematics into arithmetic. Nor did it occur to Russell in Principia Mathematica. Skolem perhaps came closer in his 1923 paper on primitive recursive arithmetic, where he pioneered the language/meta-language distinction employed by Gödel. Skolem first introduced a formal system with objects defined by primitive recursion, and then introduced another one on top of it that proved properties of objects in the first system. But even Skolem did not code one into the other.
When later asked when he became interested in the completeness problem and what where his influences Gödel replied "1928", and "Hilbert Ackermann: Introduction to math Logic, Carnap: Lectures of math Logic". Carnap, the rising star of logical positivism who Gödel met at the Vienna Circle in 1928, introduced him to logic, in particular to the issue of completeness. The book presented Hilbert's programme, and stated completeness of the first order logic as an open problem, Gödel proved it the next year (it was missed by Skolem, from whose results it quickly follows). And some time in early 1930 he had the incompleteness breakthrough, in August he mentioned his negative result to Carnap. The immediate run up to the proof of the incompleteness theorem is described in Goldfarb's On Gödel's Way In.