The notion of paladin-equivalents for alignments other than Lawful Good began with the article "The Anti-Paladin NPC" (by George Laking and Tim Mesford) in Dragon Magazine #39 (July 1980), which introduced a Chaotic Evil version to serve as an antagonist to the players. This article resulted in a terse rejoinder by Gary Gygax in a letter appearing in issue #41: "The anti-paladin is as useful as a third leg. Paladins were designed to counter balance the weight of evil monsters in AD&D. If DMs must resort to such, to control their games, why not use a 16-ton block instead? It is at least as subtle and rational." Despite Gary's displeasure, this article was included in The Best of Dragon Magazine Volume 2 collection in 1981!
Moreover, paladin-equivalents soon became official in D&D with the BECMI 'Green Box' Companion Set in 1984, which not only allowed Lawful (BECMI D&D had a single-axis three alignment system) wandering fighters the option of becoming a Paladin after reaching name level, but also allowed Neutral wandering fighters the option of becoming a Knight in service to a secular liege rather than a Lawful church, while Chaotic wandering fighters were granted the option of becoming an Avenger in alliance with a Chaotic church.
An article titled "A Plethora of Paladins" by Christopher Wood in Dragon Magazine #106 (February 1986) introduced paladin equivalents for the other seven alignments (noting explicitly the earlier article on "anti-paladins").
It should be noted that articles in Dragon Magazine were not equal to official rules, and AD&D 2nd edition maintained the LG-only alignment for paladins.