Rashi in parshas Toldos (25:27) tells us about Esav:
יודע ציד: לצוד ולרמות את אביו בפיו, ושואלו אבא היאך מעשרין את המלח ואת התבן, כסבור אביו שהוא מדקדק במצות׃
who understood hunting: [He knew how] to trap and to deceive his father with his mouth and ask him,“Father, how do we tithe salt and straw?” His father thereby thought that he was scrupulous in his observance of the commandments (Tanchuma, Toeldoth 8). (emphasis mine)
Apparently, the Avos were careful to separate maaser. But who did they give their maaser to? Though we find Avraham giving a tithe to Shem who was a Kohen of sorts (see Beraishis 13:20 with Rashi there), that was in a situation of dividing war spoils.
Since the separating being discussed here is the regular tithes of all crop yields--if it was for Shem, then it should've been referred as "Teruma." Were there Leviim at that time too?
I would be intrigued to hear an answer.