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 Megillah (29a) says that we say it specifically before purim. The reason for this is to combine the themes of destruction of Amalek present in both. (Rashi to Mishna). 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" this can either be translated as constantly or regularly.