Terry Pratchett (and Neil Gaiman afterwards) seems to have popularized the idea of gods as supernatural beings that require belief in them to exist. But is this idea truly original to him? Or are there earlier literary examples of this?
The idea of gods getting their power from the number or strength of their believers is definitely not original to Pratchett, in fact it's older than him.
The earliest use in sf that I can place on top of my head is by the Belgian fantasy and horror writer Jean Ray (I don't think many of his works have been translated into English, if any). In Malpertuis (novel, 1943), Greek gods, titans and other supernatural beings are almost dead due to the lack of believers. The movie Malpertuis is based on the book; I haven't seen it, but from the summary I think it has the same plot element. Ray wrote:
Les hommes ne sont pas nés du caprice ou de la volonté des dieux, au contraire, les dieux doivent leur existence à la croyance des hommes. Que cette foi s'éteigne et les dieux meurent.
Men are not born of the whim or will of the gods, on the contrary, gods owe their existence to the belief of men. Should this belief wither, the gods will die.
This is supposedly inspired by a quote by Voltaire: “de la croyance des hommes sont nés les dieux” (gods are born of the belief of men). I haven't found a precise reference, so Voltaire may not have actually written this (French speakers often attribute quotes to Voltaire by default).
TVTropes (thanks Bill) cites roughly contemporaneous stories by Lord Dunsany. In Poseidon (collected in In the Land of Time and Other Fantasy Tales), Poseidon is diminished and dies from the lack of worshippers. Some of the stories in Time and the Gods may play on that concept, though I don't think gods do need believers to survive in that universe.
An earlier example is H.P. Lovecraft's Elder Gods, who come when called. This isn't exactly the same idea — the Elder Gods are not exactly on the same plane as gods from Greek, Hindu, Jewish, and other real religions, and they are not so much powerless as asleep.
1940: The earliest source I know of for the "Gods Require Belief" idea is Lester del Rey's short story "The Pipes of Pan", first published in the Unknown Fantasy Fiction, May 1940, available at the Internet Archive.
Pan burying his last worshiper:
Pan's great shoulders drooped as he wiped the last of the earth from his hands. Experimentally, he chirped at the cricket, but there was no response, and he knew that the law governing all gods still applied. When the last of their worshipers were gone, they either died or were forced to eke out their living in the world of men by some human activity. Now there would be hunger to satisfy, and in satisfying it, other needs of a life among men would present themselves. Apollo was gone, long since, choosing in his pride to die, and the other gods had followed him, some choosing work, some death.
How other gods made their living:
Well, if work he must, work he would. The others had come to it, such as still lived. Ishtar, or Aphrodite, was working somewhere in the East as a nursemaid, though her old taste for men still cost her jobs as fast as she gained them. Pan's father, Hermes, had been working as a Postal Telegraph boy the last he'd seen of him. Even Zeus, proudest of all, was doing an electrician's work somewhere, leaving only Ares thriving in full god-head. What his own talents might be, time alone would tell, but the rippling muscles of his body must be put to some good usage.
As you might expect, Pan finds a career in music. He drops the syrinx and takes up the clarinet:
Out on the floor were his worshipers, every step an act of homage to him. Homage that paid dividends, and was as real in its way as the sacrifices of old; but that was a minor detail. Right now he was hot. He lifted the instrument higher, drawing out the last wild ecstasy from it. Under his clothes, his tail twitched sharply, but the dancers couldn't see that, and wouldn't have cared if they had. Tin Pan Faunus, Idol of the Jitterbugs, was playing, and that was enough.
TL;DR: The trope is almost as old as fiction itself.
The ancient Babylonian flood myth, The Epic of Atrahasis, which inspired the better known Epic of Gilgamesh and the biblical flood narrative, was written circa 1800 BCE. In this story, the gods wipe out humanity with a global flood, then find themselves starving to death because, with no humans left to offer sacrifices, they can find no sustenance. When the lone survivor finally makes landfall and offers a sacrifice, they descend on it "like a swarm of flies".
The Anunnaki, great gods,
were sitting in thirst, in hunger...
Ninti wept and spent her emotion;
she wept and eased her feelings.
The gods wept with her for the land.
She was overcome with grief,
she thirsted for beer.
Where she sat, the gods sat weeping;
crouching like sheep at a trough.
Their lips were feverish with thirst,
They were suffering cramp from hunger.
- Atrahasis OB III, 30–31
The next portion of the story is missing from the extant copies, but when it picks up, we read:
The gods sniffed the fragrance
and gathered like flies over the offering.
- Athrahasis III
We can fill in the blanks by reference to Gilgamesh:
Then I sent out everything in all directions and sacrificed (a sheep).
I offered incense in front of the mountain-ziggurat.
Seven and seven cult vessels I put in place,
and (into the fire) underneath (or: into their bowls) I poured reeds, cedar, and myrtle.
The gods smelled the savor,
the gods smelled the sweet savor,
and collected like flies over a (sheep) sacrifice.
- *Gilgamesh, XI
The issue here isn't "belief" so much as "homage" - belief never factors into the story. But clearly, the Anunnaki, the great gods of the Athrahasis, require sacrifices from humans to survive. And considering the fact that Athrahasis was written no later than 1800 BCE, we have an example here that predates all the others provided - by nearly 4,000 years.
There's a reference to this idea in Harlan Ellison's story "Working with the Little People," (written in 1977) collected in Strange Wine. The story itself is about how the gremlins need belief to stay alive, but the narrator implies that Nietzsche stated this theory:
It was simply the Nietzschean theory all over again. Nietzsche suggested that when a god lost all its worshipers, the god itself died. Belief was the sustaining force. When a god's supplicants went over to newer, stronger gods, belief in the weaker deity faded and so did the deity.
Douglas Adams kind of did a throwaway parody of the idea when describing the Babelfish in Hitchhikers Guide to the Galaxy (1979):
Now it is such a bizarrely improbable coincidence that anything so mindbogglingly useful could have evolved purely by chance that some thinkers have chosen to see it as a final and clinching proof of the non-existence of God.
The argument goes something like this: "I refuse to prove that I exist," says God, "for proof denies faith, and without faith I am nothing."
"But," says Man, "the Babel fish is a dead giveaway isn't it? It could not have evolved by chance. It proves that you exist, and so therefore, by your own arguments, you don't. QED."
"Oh dear," says God, "I hadn't thought of that," and promptly disappears in a puff of logic.
That pre-dates Discworld by four years.