superman wasn't about fighting most of the time, neither is batman, I think that's what seems obvious when you think about game mechanics and the reason so many comic remakes fail. trying to fit comics into some genre is what is worse for it. you could just as good say 'hey, he has a bat car/jet/..., lets make it a shump. and while it could be even fun to some degree, it's not really exploiting what batman is about.

so, superman is not a fighting comic/movie, although we remember those showdowns, I think it was most of the time investigation and an increasing danger. you have to put a lot of effort into figuring out whats going on, that's what made superman so good. you have all the strength, yet all the weakness of a living form. you cannot be at two places at the same time, you cannot make things 'unhappen', you cannot protected your family 24/7.. superman is still not almighty.
the showdown was usually best, when it seemed to be impossible for superman and then he flew faster than light back in time or moved his arm/body so fast, it vaporized and could pass some....
you have to read the comics to get a feeling what it is about. batman isn't really about beating up bad guys (although that also happened), it's about gadgets that to some degree seem silly, yet believable in the scope of the comic, so you enjoy him using those. but most importantly, batman is a stealth badarse, I think no other company before got that right.
superman is indeed more difficult to fit into a game, it is about finding solutions to difficult problems, to gather informations, to....

One idea I'd have is, imagine a super villain says 'I gonna destroy the city in 24h'. let's assume the player does not spoil what's going on by reading online some solutions. so, now there is a city (can be procedurally created). you know, there is somewhere a threat, you know, there is probably some villain hiding. you can now go everywhere, you can see through walls, yet you can't know where he is nor how he will destroy the city.
walking around and looking through falls is kinda random, you won't scan hundret of thousands of houses and check 10million ppl. you can't just look for an a-bomb. you have to find smarter ways, e.g. if there is a robbery, instead of catching that one guy, you could try to follow him, he probably has some connections to sell those.maybe you'll find some bigger place they sell the stolen goods, there is probably a leader of that place, you could follow him, maybe....

but it's probably not that exciting anymore for most of the people and setting up a city with tons of solutions isn't really do-able, you'd have to really simulate it to give the player the choice of solving that.

Can playing as Superman, or any similar character who is basically unbeatable, be fun?

So we are talking about invincibility, rather than immortality per se?

Yes, I think an invincible character can be fun to plan. In fact, video game characters are (with few exceptions) effectively invincible already - checkpoints, save games and auto-recharging health bars are all a form of invincibility, where defeat is only a minor setback, and you re-enter the fight refreshed and reinvigorated.

Apart from a few odd games with perma-death (Diablo's hardcore mode, for example), death is really little more than a delaying mechanic in contemporary games.

Superman isn't as much as a detective as Batman, so a puzzle game with a theme of cleverness might not be appropriate, but instead Superman is all about being a helpful nice guy, so he would fit right into that kind of game where the goal is to solve the personal problems of the other characters.