In our own society, Nuteena (a meat substitute mainly made from peanuts, soy, corn, and wheat) was based on the 1896 formula for Nuttose, sold by "the other Kellog brother", not the one who founded the modern cereal company. Later, Loma Linda Foods offered a number of meat subtitutes starting in 1949; they were later bought out by their competitor, Worthington, which was bought out by the modern Kellog's cereal company in 1999.
Therefore, it's safe to say that meat substitutes fairly similar to those I grew up with in the 1960s were possible as soon as the nutritional value of peanuts had been recognized and the foundations of separating foods into starches and proteins laid down. In our history, that took place from the late 19th century through the first half of the 20th, but all the crops and techniques were available after the colonization of the Americas (peanuts were a New World crop) and the opening of the Far East (soy was from eastern Asia). As an example, I recall my parents making "gluten steaks" from plain wheat flour in our home kitchen between 1970 and 1973; these techniques could have been applied (albeit producing nutritionally incomplete proteins unless a mixture of grains and legumes was used) even in the pre-Classical ancient world, given the knowledge.
For less "analog" substitutes, the Chinese made tofu as far back as the 2nd century BCE, and cheese (which is nutritionally a reasonable substitute for meat and, while animal derived, doesn't require slaughtering the animal) has been around longer than that.