Adam wasn't allowed to eat meat. After the mabul (Flood) we were suddenly permitted to eat (Bereshit 9:3). What changed (ie what was the reason we weren't allowed to before, why are we allowed to now and what changed after the flood)?
Rav Simcha Wasserman explains why after the Mabul he began to eat meat. R’ Wasserman says this indicates the new lower level of Kedusha. The sin of that generation was stealing. After the Mabul, the world continued but on a new lower spiritual level. Man now had to depend on another creature’s flesh for survival, Mida K’neged Mida for the sin of stealing. The meat, representing heavy physicality, reminds us of where we are and where we could be. Although this represents a bleak picture for mankind, there is a tikkun, for everything in Judaism. The potential for tumah has an equal potential for kedusha. When a righteous individual is nourished by food derived from an animal, the food is elevated immeasurably.
The Sforno says the world had been in a state of perpetual spring before the flood (hence lifespans in the hundreds of years), and thus the world was such that humans didn't need to eat meat to stay healthy. After the flood, it was needed.
I believe it's Rav Kook who suggests that before the flood, people forgot that there was any distinction between them and animals; after the flood came the reminder, yes killing animals for food, no killing people.
The Midrash Agadah (attributed to Rabbi Mosheh HaDarshan), also quoted by Torah Temimah (note 66), answers that the reason why Adam wasn't allowed to eat meat was because before he sinned, everyone (including animals) was supposed to live forever. Therefore, he wasn't permitted to remove a life from the world. After his sin, it was determined that everyone (including animals) would eventually die. Therefore, from the time of Noach, he was allowed to kill an animal for his benefit since it would die anyway. The reason why it wasn't permitted to Adam immediately after his sin is so that a person doesn't rise in status as a result of his sin.
Tosafot (Sanhedrin 56B) says that Adam HaRishon was able to eat meat that had died by itself he just was not able to kill the meat and eat it. However, if one of the limbs of the animal fell off by itself, he was not allowed to eat it, because of the prohibition of Ever Min Hachai.
Rambam holds that Adam wasn't given the prohibition of Ever Min Hachai. The Kesef Mishna explains that this is because Adam wasn't permitted to eat meat at all.
Rashi on Chumash (Genesis 1:30) says that Adam and Chava were not allowed to "kill animals and eat meat", and commentaries disagree on the exact scope of this prohibition. The Gur Aryeh (quoted here) says that Rashi is saying that Adam was forbidden to eat meat at all. The Mizrachi says that Rashi is saying that humans were only not allowed to kill animals, (quoted here, original here).
R' Yehuda Ben Besaira says (Sanhedrin 59B) that while Adam HaRishon was in Gan Eden, the angels roasted meat for him.
Here are the stages of eating meat:
Adam: According to Tosafot, Adam was allowed to eat meat that had died on their own, but was not able to kill animals and eat them. According to others, he was not able to eat meat at all.
Noach: The Ramban (Genesis 1:29) explains that all the animals were supposed to die in the flood. Since they only survived because Noach saved the animals from extinction, Noach was given the right to kill meat and eat it, but was not allowed to eat the limb of a living animal. As the Ramban puts it, Noach was only given control over the animals body, not the soul. This prohibition included not drinking the animals blood while the animal was still alive (Bereshit 9:4 and Rashi there).
Jews: The Torah was given and the Jews were given additional restrictions.
- They were not only not permitted to eat the limb of a living animal, but even after the animal was dead they were not allowed to eat the blood, since the blood is the soul (Vayikra 17:10 and on).
- They had to ritually slaughter the meat, they were not allowed to just kill it. (Devarim 12:21 - see Rashi)
Jews in the Desert vs. Jews in the Holy Land: While the Jews were in the desert, there is an argument (Gemara Chulin 16B-17A) between R' Akiva and R' Yishmael regarding whether the Jews were able to eat regular meat (Called "Meat of Desire" as opposed to sacrificed meat). R' Yishmael says that the Jews were not allowed to just slaughter an animal and eat it. The only way they were allowed to eat meat was by offering a sacrifice and then eating the leftovers. (Vayikrah 17:1-9 - and Rashi on Devarim 12:20).
Once they entered the land however, they were permitted to slaughter and eat meat without having to bring a sacrifice, since the distance to the Beis Hamikdash was too great to expect the Jews to go to the Beis Hamikdash every time they wanted to eat meat. This is the opinion Rashi brings (Devarim 12:20-21).
R' Akiva disagrees. He says that the laws of Shechita didn't start until the Jews entered the land. In the desert they were able to just kill the animal and eat it. Only a sacrifice had to be ritually slaughtered. Once they entered the land, they were only allowed to do Shechita before eating the animal. The Rambam rules according to Rabbi Akiva in Hilchos Shechita 4:17-18.
In Likkutei Sichos Volume 4, Parshat Re'eh (this is in Yiddish, if anyone has a link to a hebrew translation, please add it), The Lubavitcher Rebbe notes that Rashi brings the opinion of Rabbi Yishmael, but also brings the reason of Rabbi Akiva. The Rebbe explains the root of their disagreement, how Rashi could combine the two opinions and teaches how we can apply that to our daily service and spiritual endeavors. (See an English translation here).
As an aside, here is an interesting article from the Journal of Halachah and Contemporary Society regarding Vegetarianism From A Jewish Perspective. This article also touches on some of these issues.
Noach's generation had forgotten the difference between humans and animals (in the generation of the flood, people drew up marriage contracts between two men, or between people and animals). Telling Noach that people could eat the flesh of animals was intended to drive home the distinction between humans and animals.
Ralbag in his commentary to Genesis 1:29 explains that nothing changed, and man was in fact allowed to eat meat all along. He quotes the Talmudic statement that there was in fact a change, and says that this exposition of some of the Sages is "an utter falsehood from which it is fitting for every man of intelligence to flee". He argues that it is a philosophical impossibility for the Divine Will to change (by first forbidding meat and then permitting meat), and asserts that in these types of matters we only accept that which accords with the principles of Torah and philosophy regardless of who says it. We are not obligated to accept everything the Sages say, because we already see that they sometimes contradict each other which indicates that some of their statements on these types of matters might not be correct:
והנה מה שאמר ויאמר אלהים הנה נתתי לכם את כל עשב וגו' הוא בריאה ונתינת טבע לא מצוה והעד הנאמן אמרו בסוף הענין ויהי כן ואופן הבריאה הזאת הוא שנתן בכח האדם שיהיו הצמחים מזון לו עם היותם רחוקים מאד מטבעו וכן נתן זה הכח לשאר הב"ח ומזה המקום יסור הספק אשר יסופק מזה המאמר וזה שהוא מבואר מצד העיון ומצד התורה שהרצון האלהי לא ישתנה וכבר יחשב שיחוייב מזה המאמר שישתנה רצון השם במה שיצוהו מהמצות וזה שכבר יחשב שהשם יתברך מנע בזה המאמר אכילת בשר לאדם ואחר כן התירו לנח במאמרו כל רמש אשר הוא חי לכם יהיה לאכלה וזהו שקר עצום ראוי שיברח ממנו כל בעל דעת וכבר אמרו זה בדרש קצת רז"ל אלא שבאלו הענינים ובכיוצא בהם לא נביט למאמר אומר כמו שהורנו הרב המורה אבל נמשך אל מה שיאות על שרשי התורה והעיון והוא מבואר שאין ההאמנה בכל מה שאמרוהו רז"ל מחוייבת לנו כי כבר ימצאו להם דברי סותרים קצתם קצת ולזה לא נרחיק היות בהם דברים בלתי צודקים בכמו אלו הדברים
In addition to the sages' thoughts on this, as mentioned by other answers here, another possibility is from the Tenakh itself, in Bereishit 3, as animals were used for human purposes:
"Then Ad-nai El-him made garments of skin for Adam and his wife and clothed them."
Additionally, shortly after the garments of skin, the first instance of divine approval of animal death for sacrifices appears:
"And Abel also brought an offering—fat portions from some of the firstborn of his flock. Ad-nai looked with favor on Abel and his offering."
If, by this time, animals were being used for clothing and for offerings, and both were approved by G-d, one may suggest using animals for food was likewise approved.
edit: And by Bereishit 9, G-d formally approves of eating animal flesh for food. Whether animals were used for food prior to this is speculation based on Bereishit 3 and 4, where animals are used for clothing and sacrifices.