tl;dr Shōnan Bakusōzoku, an OAV from 1986 with 12 episodes and 12 endings (ended only in 1999).
Intro
I took up Gao's suggestion and used ANN's API to create a duplicate of their database and then search for all titles that have as many OPs/EDs as they have episodes. If anyone is interested in the code for this (it's not nice :P) and all results, go here.
Assumptions
I restricted the analysis to titles that have at least 6 episodes. ANN's episode field sometimes contains additional information such as '10 (+2 Specials)', in which case I only take the first number and ignore the rest. There are no checks for the title or anything like that: if ANN lists an ending twice or if the same ending appears multiple times with different artists, those all count as separate. Most importantly, the relevant date is the start date (because that is less parsing work and because often there is no end date given).
Results for EDs
Below are the results. With the above restrictions, ANN has 30 animes that fit the bill and the oldest of them is Shōnan Bakusōzoku. Note though, that the final episode is from 1999! Among the first few, Iczer Reborn ended on February 25, 1991, already, so maybe that's your winner? See here for the full table.
Huh, more endings than episodes?
You may have noticed, there are titles with more endings than episodes: They can all be considered to have as many endings as episodes. For Ten Tokyo Warriors, Sakura Wars 2 and Heaven's Lost Property those are caused by some kind of inconsistent annotation in ANN. For Akikan! they list an extra ending for a special but don't count the special towards the episodes. Katanagatari got an extra ending for the noitaminA rebroadcast. For Highschool of the Dead and Maken-Ki! Battling Venus they count the OAV ending towards the anime.
Almost made it
I thought it would be interesting to also check which ones cut it very close. Here's an addtitional list sorted by #EPs/#EDs
and then sorted by vintage. I left out all that have a quotient of 1 or less, since we already know those from above. The full list can be found here.
As ʞɹɐzǝɹ already mentioned, Lucky Star should qualify for the previous list, having 24 episodes and endings, but ANN is missing the ED for episode 22, and so on. As you can already see, this DB isn't perfect either ;)
Overview
Finally, here's a bar plot showing the distribution of the number of endings among all animes that fit the assumptions described initially.
Results for OPs
There are only two results for #EPs = #OPs
, and those are already shown in the list above (Sakura Wars 2 and Angelique: Twin Collection). The results for #EPs / #OPs
are here. OPs are generally not as diverse:
More OPs than EDs and vice versa
As per Gao's second suggestion: there are 221 animes with #OP > #ED
, among those 115 have no endings listed in ANN at all, which is probably a mix of the truth and missing annotations (full list). The other way around, there are 781 animes with #ED > #OP
, 82 with no openings at all (full list).
Outro
This is not the definite answer either of course. ANN doens't provide an XML schema, so I might have overlooked something, and even if everything went well in my parsing, we already know they have a different opinion on the number of EDs, e.g. for NGE (see Gao's answer for that discussion), and there are several errors mentioned above. Answering a different question I realized I should have probably made sure the endings are unique, but that doesn't affect the main results here though.