A modern misconception was that Gutenberg invented printing; this was not the case. Woodblock printing was a craft over a thousand years old when he came about.
Another misconception was that Gutenberg invented moveable type; this was not the case either. Moveable type was invented four hundred years before Gutenberg's time in China, and made its way to Europe eventually.
What Gutenberg did invent were various tools and procedures to print more, faster, and cheaper (most importantly the hand mould and the printing press, which significantly sped up the process). This allowed European printing to catch up with Chinese/Korean book production, and eventually overtake it.
So it is more appropriate to look at Gutenberg's work as a big evolutionary step, not actually a revolution. He didn't invent all of it in a blaze of divine inspiration; he (significantly) optimized existing processes.
There were corroborating factors that helped the "taking off" part in Europe.
One of them was already brought up by @Semaphore -- alphabets (prevalent in Europe) are easier to set in print than syllabaries or logograms, as there are fewer glyphs to chose from. This is a gradual quality, though; it is certainly possible to use moveable type with e.g. the Chinese writing system (see above).
Another factor favoring Europe was the high demand by wealthy patrons for one specific, large book -- the bible -- offering high potential profits that could be re-invested.
So... yes, it could have happened earlier, or in a different place of the world. It did happen in other places, to be exact -- it just did not "take off" the way it did in Europe.