The very first Mishnah (Berachot 1:1) states that the earliest time for the recitation of the evening Shema is the time that kohanim can eat terumah:
מאימתי קורין את שמע בערבין משעה שהכהנים נכנסים לאכול בתרומתן
The Talmud (Berachot 2a) attempts to figure out what time this refers to:
אמר מר משעה שהכהנים נכנסים לאכול בתרומתן מכדי כהנים אימת קא אכלי תרומה משעת צאת הכוכבים לתני משעת צאת הכוכבים מלתא אגב אורחיה קמשמע לן כהנים אימת קא אכלי בתרומה משעת צאת הכוכבים והא קמשמע לן דכפרה לא מעכבא כדתניא ובא השמש וטהר ביאת שמשו מעכבתו מלאכול בתרומה ואין כפרתו מעכבתו מלאכול בתרומה
The Master said: FROM THE TIME THAT THE PRIESTS ENTER TO EAT THEIR 'TERUMAH'. When do the priests eat terumah? From the time of the appearance of the stars. Let him then say: 'From the time of the appearance of the stars'? — This very thing he wants to teach us, in passing, that the priests may eat terumah from the time of the appearance of the stars. And he also wants to teach us that the expiatory offering is not indispensable, as it has been taught: And when the sun sets we-taher, the setting of the sun is indispensable [as a condition of his fitness] to eat terumah, but the expiatory offering is not indispensable to enable him to eat terumah. (Soncino tranlation)
This reasoning seems a bit circular to me. We only know that the time for Shema is tzeit hakochavim because that is the time for kohanim to eat terumah, but we only know that that is the time for kohanim to eat terumah because that is the time for Shema. So how do we know either one in the first place? According to the Talmud it appears that this Mishnah is the source for both the time for kohanim eating terumah being tzeit hakochavim and the time for Shema being tzeit hakochavim (from the fact that the two events are equated), yet the Mishnah doesn't mention tzeit hakochavim at all! It seems like we're going in a circle — we derive the time for Shema from the time for eating terumah but we then derive the time for eating terumah from the time for Shema. Thus, we seem to have no original source for either one stating that the time is tzeit hakochavim.
If the above wasn't so clear, we can rephrase it as follows:
The whole point of this Mishnah is to tell us the time for Shema. That means that prior to this Mishnah we don't know the time for Shema. The Mishnah tells us the time for Shema as a function of the time for eating terumah in order to also teach us the time for eating terumah (by informing us that it's the same as the time for Shema), which means that prior to this Mishnah we are not supposed to know the time for eating terumah either. The problem is that if prior to this Mishnah we don't know either time, then telling us that the two times are the same doesn't actually tell us what the time is. All we should know after reading this Mishnah is that Shema can be recited when terumah can be eaten and terumah can be eaten when Shema can be recited. But we should have no way of knowing that that time is tzeit hakochavim.
How can we understand how we derive the times for eating terumah and reciting Shema from this Mishnah?