It's not canonical, or even canon-consistent, but the prototype of the replicator idea appears in David Gerrold's 1980 ST novel The Galactic Whirlpool
, which is apparently meant to take place immediately before "The Trouble With Tribbles" (or at least, I believe Gerrold has said so in recent years; the only connection is a reference on the last page to setting course for station K-7). He portrayed the tables in the rec room containing built-in devices that used transporter technology to deliver the food (though it took about a minute, and it was unclear whether the food was actually assembled from raw materials or simply prepared elsewhere and beamed to the table). Since Gerrold was one of the developers of TNG, he may have been the one who worked the replicator concept into the premise.
Shane Johnson's 1987 Mr. Scott's Guide to the Enterprise
describes a similar technology in use in the movie era, claiming that "Nutritech Corporation's new food processor system" combined centralized "food synthesis machinery" that assembled convincing foodstuffs from basic nutrients (not unlike ENT's "protein resequencer") with micro-transporters that beamed the synthesized food to the various delivery slots around the ship. This was an updating of the food-delivery system described in The Making of Star Trek
, in which the food was mechanically prepared from real, perfectly preserved ingredients and delivered to the food slots by a sort of turbo-dumbwaiter system inside the walls. (Although in the light of ENT, we can now assume that protein resequencing was used instead of or in addition to real-food storage.)
Of course the Galactic Whirlpool
version can't be reconciled with canon, but if we accept Johnson's premise for the sake of argument, that would mean that they didn't technically have replicators in the movie era, but they had something very close. The main difference between Johnson's food processor and a replicator is that the latter uses transporter technology to create the food (and other objects whose patterns are stored) from raw molecular stock, so that assembly and delivery are combined into a single process. But it seems to me that Johnson's processors would've been close enough to replicators that there wouldn't have been too many decades between them.
It's worth noting that the term "replicator" didn't actually get used in TNG until the second season. According to the twiz.com script database, the term was first used in "The Child," and both its second-season references (that and "Samaritan Snare") are to replicators as devices for creating technology rather than food. "The Survivors" was the first episode to refer to a replicator by name and assert that it was used to make food, with "Hollow Pursuits" being the second. In the first three seasons, the devices are generally referred to by the term "food dispenser," or occasionally "food station" (twice, by Riker) or "food slot" (by Crusher and the computer in "Evolution," and in occasional script instructions through season 5). "Food terminal" was used by Jarok in "The Defector." The transitional "food replicator" was used in "Sarek," but it had just become "replicator" by "The Most Toys" (at least in script directions).