Prior to the story of Purim was there a special yearly reading of Parshas Zachor? At which point in history was it instituted to read Parshas Zachor before Purim?
The Gemara derives via drasha an obligation to read zachor. Accordingly they must have said it even before Purim. They specifically started saying it before Purim sometime before the time of the Mishnah, for the Mishna in Megilah 29a says that we specifically say it before Purim. The reason for this is to combine the themes of destruction of Amalek present in both (Rashi on 30a).
However the original obligation didn't have a specific time attached to it (see Rambam Sefer HaMitzvos: Assei 189; Hil. Melachim 5:5). Rambam (there) fascinatingly cites Shmuel's exhortation to destroy Amalek in the context of this mitzvah. (I Samuel ch. 15). This was definitely not a regular scheduled event. Rambam does write (there) that the mitzvah is to remember Amalek "tamid" which can either be translated as constantly or regularly.