By this I mean have a piece of the opening credits that changes every episode/from time to time.
I know it’s a bit chic to do it now between Simpsons, Frasier, American Dad, etc. but how far does this trope go back?
You’ll have to quantify ‘time to time.’ You list Frasier, but to my knowledge, Frasier only changed the opening every season, rather than more often. Plenty of shows had different openings from season to season (most 80s sitcoms, for instance). If you narrow it to every episode, it may be easier to quantify.
The color of the word “Frasier” changed from season to season, but whatever happened to the Seattle skyline was different every episode (for the most part, they had about 10 or 15 go-to sights gags that they recycled)
And I’m not talking about just changing the credits every other season, I mean a consistent change every (or almost every) episode
I don’t know if it counts or not, but the ottoman gag on “The Dick Van Dyke Show” might be an early possibility. I’ve heard that it was random whether he tripped over it, side stepped it, or maybe even other possibilities, but I think they only had two or three possibilities and not one for every episode.
The opening credits of Mission: Impossible had an edited montage of scenes from that episode behind the fuse burning across the screen. So, different every time.
Three versions: sometimes he tripped on the ottoman, sometimes sidestepped it, and sometimes sidestepped it but then tripped on the carpet.
The Rockford Files had a different answering machine gag at the beginning of every show.
The Mickey Mouse Club of old had various ways of Donald attempting to ring the gong.
There was a great moment on Diagnosis Murder when Dr. Sloan and Steve were visiting a crime scene and Dr. Sloan said “I almost tripped on that ottoman!” Great little tribute to his old show.
Oh, good one!
More recent than many mentioned here, but Animaniacs had several different versions of the last line of the theme song.
Dana Delany!
Gonzo’s trumpet was my first. 
That was my favorite part of the show!
Fawlty Towers had a chalkboard gag (actually billboard) with a different anagram of the hotel name each episode.
It probably didn’t beat Dick van Dyke, but Car 54, Where Are You? featured Toody and Muldoon doing something different inside their squad car during the opening credits of every episode, IIRC.
This is what I came in to mention. The opening to the MIckey Mouse Club was the same every week*, except for the “Donald rings the Gong” gag at the end, which changed from wek to week. I don’t know of any earlier examples.
*It wasn’t until I heard the entire “Mickey Mouse Club” theme on a Disney record that I realized it was a LOT longer than the theme I grew up hearing on TV. But I saw it in syndication, not during its initial run, and syndicated shows tend to have the openings cut down in length or even changed altogether (as I Love Lucy did). So I found a copy of the Mickey Mouse Club DVD and saw that they had the entire opening there – much longer than I’d ever seen. And it was in Color! Even though the show was broadcast in black and white, Walt knew that technology was developing, anmd had the thing animated in full color. Unfortunately, I think there’s only the one “Gong Gag” on the DVD.
My favorite, of course, being ‘Farty Owls’.
Flowery Twats