It’s always possible. Not always pretty, but possible.
Also my wife would not go for visible Ethernet run like that. I'd have to hire a contractor to do drywall work to have it done right.
I have managed to get Ethernet everywhere I want for the most part though, thanks to a luckily positioned unfinished half of the basement and garage, where visible cables are fine and I can just pop through walls here and there.
Obviously this is always a cost issue (ie it’s subjective exactly how nice it has to look and what is acceptable to pay), but it’s far from impossible to run ethernet or fiber without breaking down walls.
The cheap version of this is having new covered cable channels running on top of existing baseboards and door trims. The more expensive version would be to either replace or carve out space in the boards to fit the cable, in that case you would never see it except when it exits the board to an outlet.
Obviously a bit late for this, but I don’t understand, if there’s “coax to nearly every room” how can it also be “not feasible” to run new cables?
If nothing else surely you could just run ethernet or even fiber in the physical channels now used by coax? Especially if the alternative is setting up an entire switching set up for moving ethernet over coax.