(contains spoilers)
My questions are: Is there a non-cheating / non-(mis)using exploits way to defeat Gedna Revel? Does it really get harder the higher the player level is (this is what UESP says)? Or how long does it take to exhaust her spell points by evading her spells? -
When I played Tribunal for the first time, not long after it was released, I went to Mournhold with a character who had defeated Dagoth Ur already, with a level in the thirties, if I remember correctly. After a while, the character level was in the low fourties, this character stumbled upon Gedna Relvel. I discovered soon that this lady was no ordinary opponent. It was almost impossible to hit her effectively both with weapons and spells, and she had one-hit-kill spells. On the other hand her attacks were relatively easy to avoid, by running away and/or hiding behind columns for example. I tried to exhaust her spell points by evading her spells, but I gave up, because her spell points lasted longer than my patience (after several hours of trying again and again).
Recently I created a new character and went back to Gednal Relvel, this time on level 32. I had read the UESP entries about Gedna Revel, and knew that it would be almost impossible to defeat her. And I failed again, although I tried most recommendations I had read somewhere, mostly because my character couldn't survive a single hit of her spells. I see two possibilities: To fortify strength, or to try a powerful reflect spell. Which requires fortify magicka, which in turn requires lots of spell points.
I decided to use the console. I increased the hit points (originally in the 200's) to 5000 and went into the fight with Gedna Relvel. The first thing I noticed was that her spells cause damage in the 300's - no surprise that my character didn't stand a chance to survive them, wasn't even close to surviving them. Again, to fortify strength to an amount required to survive Gedna Relvel's attacks without cheating or using exploits would require a huge amount of magicka, a lot more than I think is within the scope of my character with its uncheated strength and magicka in the 200's.
It took a while (and a total amount of cheated hitpoints somewhere in the range of at least 20-30,000 - I didn't try to minimise this number) to defeat Gedna Relvel, but of course I'd like to do the same without cheating, without using the console, if this can be done with an acceptable effort.
Any ideas?

Have you tried focusing on Spell Absorption?

The Ring of Equity (100% absorption for 30 seconds) should do the trick, the quest that gives this is part of the House Telvanni story.

Interesting - I might give it a try. Means to do the Telvanni questline from the beginning - shouldn't be too much of an issue, but takes some time.
According to UESP, the ring has two charges only before depleting. 60 seconds of spell absorption (is there anything to reflect?), at the same time 60 seconds to inflict damage. When I do it the way I did it with the cheated hit points (with a melee weapon), this is not going to be enough time. Looks like I have to come up with something.
Thanks!

Gedna Relvel is actually bugged and is not supposed to get exponentially harder like she does in the base game and there exists at least 1 fan made patch slash mod that fixes so that she isn't so broken.
Here's a link to the mod I know about: http://mw.modhistory.com/download-26-15200 it makes here scaling far less broken, but it doesn;t gimp her either,so it just makes it fair.

Then there is also this mod
https://www.nexusmods.com/morrowind/mods/44121
Which makes her stats fixed so she doesn't scale at all

Thanks - will try the first mod (and possibly the second one, too).

Update: The first mod makes Gedna somewhat weaker indeed, but her spells still cause too much damage for my character: close to 300 points per hit. On the other hand, fire magic is now the most powerful weapon against Gedna (among the weapons / spells I tried). It may be possible to kill her with a sufficient supply of magicka potions, a more powerful fire damage spell than I currently have, and a lot of time (running away / evading her spells).
I'm not sure what the benefits of leveling up might be (my character has destruction and willpower at 100 already), beyond increasing health and magicka points and agility - especially when Gedna gets stronger, too.
Very interesting experience indeed!

Bring a pile of full Grand Soul Gems to the fight to refill the ring. 3 Grand souls should give you a charge plus a bit.

Some of the purchasable Soul Gems already contain souls, but most will be empty (including the Grand ones you can buy in Mournhold). As far as I recall there's only one capturable soul larger than what can fit into a Grand Soul Gem: Vivec. So using the Star is no different than using an ordinary Grand Soul Gem in the vast majority of scenarios, including this one.

Thanks.

The second mod I shared stops her scaling to your level all together so that she has fixed stats,so conceivably you could get to a point where you can easily overpower her and level without fear that she'll scale her way into godmode.Since she would have the same stats when your level 1 as say level 50.

Yes, and this is why I won't use this mod - it's not much different from using the console. I'm looking for a way to defeat Gedna Relvel using in-game means (like the method WingedKagouti pointed out), not to make my life easier.
The first mod you mentioned suits me fine, as it fixes a game bug (according to UESP), but works in line with the game design and doesn't make the lich easy prey.

I must admit that I have very mixed emotions about monsters whose strength is determined by the strength of the player character. I don't like the way it's done in Oblivion (where you level up, and out of a sudden the whole monster population changes, at certain thresholds). In addition, there is no real motivation to get stronger, at least for me. Morrowind gets it right, in my mind, but suffers from the issue that, sooner or later, not many really challenging opponents are left. I defeated Dagoth Ur at a level near 25 and with ease - to meet a Daedroth or a Golden Saint at level, say, 10 is quite a different story (although these guys can be defeated at lower levels and without cheating, if you know what you're doing).
This is why Tribunal and Bloodmoon make sense, or total conversions like Sword of The Perithia, which raise the bar considerably (or you enjoy Morrowind by simply exploring and enjoying the island and its people and politics, without being "side-tracked" by fighting, or by trying out the different player classes, or by inventing and using "house rules" like not using certain weapons, armour, spells, etc., or by playing the game without fighting).

The figures at UESP, I believe, assume an Enchant skill of 10. If you increase your Enchanting skill past that, the charge cost of Cast on Use items goes down by a percentage equal to (Enchant - 10). This means that:
at 60 skill, you get twice the uses (so 120 seconds)
at 85 skill, you get 4 times the uses (so 240 seconds)
at 100 skill, you get 10 times the uses (so 600 seconds)
at 110 or more skill, each use only costs 1 charge (at this point, it might feel like a bit of an exploit)

So, if you can raise your Enchant skill, you can keep using the ring for longer. You could do this with a trainer, practice, or perhaps using a custom spell or magic item to boost your skill temporarily. (Using a spell couild work nicely since the spell absorption effect might give you your spell points back.) You can buy spells with Fortify Skill in the Tribunal expansion if you want to make a custom Fortify Enchant effect. (Note that the effect only needs to be effective long enough to activate the ring for it to count.)

Of interest is that, unlike many of the skills in the game, the benefit per point becomes more noticeable when the skill is high; there is a noticeable difference between 99 and 100 skill.

Thanks - I admit that I never even considered a potential impact of Enchant, nor did I use Enchant with the character I'm currently using.
Definitely worth exploring and trying!