A meme is simply a particular piece of cultural information that can be transmitted through intentional repetition and conscious imitation, and over time responds to natural pressures and selection (e.g. a particular hairstyle may be fashionable and spread within a culture or a group until superseded by some other style). They're really as old as humanity- something like the burial of the dead can be regarded as memetic.

If you're thinking specifically about internet in-jokes (as Flocculencio is quite correct about the Dawkins definition), the first examples of what grew into meme language would most likely be the 1337/133t/leet speak terms used on 80s & early 90s Bulletin Board Systems. This is pre macros (any macro meme would unfortunately be too recent to be discussed in this sub - and as for phrases, "all your base" is 1998 so just too late), but the use of terms like "pr0n" for porn, which were used to get around filters, served the function of both being functional in that space, and coming to signal being part of a group that got the joke. That's implied by the term for the argot - leet is short for elite, meaning only the "elite" people can read and understand it. Which is part of the structure of memes as a medium (again, if you are talking about memes meaning the medium of internet in-jokes): they're funny because you get it.

Later memes are, as I say, outside of the scope of the sub, but if you read a little about leet, and about the forms of trolling and the kinds of in-jokes that were common to BBS communities in the 80s and early 90s, I think you'll definitely find the linguistic roots of the joke forms you're looking for.

That said, this answer is probably only helpful if that's the kind of meme you mean. Apologies if not! Alternately, you might investigate popular repeated graffiti, like 'Kilroy was here'. You might also consider Dancing Baby - I guess part of the difficulty in answering this question is, what counts as a meme?