While everyone might hate the fact that enemies also "scales" with your level, it's, in my opinion, more fair than making an enemy follow your stat
I accept this as true, but it doesn't mean either is good. Bethesda games nearly seem set up that leveling is a downside (not as much as some games *cough*FF8*cough*, but still). Luckily, they do allow you to not level up or control how you level up.
it becomes really difficult to properly tell a story in this kind of game.
The approach I've come up with and sounds good in theory is "Open World, Linear Story". Instead of having location-based triggers, have certain types of actions cause the story to move forward; doing three missions or three quests or getting to any city could trigger the first part of an overarching story. In fact, that's often what seems to happen in roleplaying in my groups; No matter where you go, the story follows.
As said above, I think BotW does a fantastic job of telling an overarching story in any order. The game tells you where each story point is, then lets you decide when and how you learn about it. The story doesn't need to be learned in order, since the point is learning it, not following it. The order you do things in
is the story. It starts and ends the same way, but how you get there is what makes it open and your story. I think an rpg could do things the same.
As for difficulty and scaling, anything that makes leveling meaningless or actively a downside seems incredible counter-intuitive. What I've liked is when games has specifically level areas and fights. What allows you to go to places above your level is;
Player skill matters more than stats
Gear mattering more than just numbers
Replaying when you know what's in the game and have a plan
But I'd like to focus on a fourth option; Missions/Quests. Areas themselves don't necessarily have to be tough anywhere. Instead, you could take what mission-based games do but don't restrict access to the world. Exploration is about that; seeing the world. That itself doesn't have to be hard or even have encounters. Instead, the story could be based around a homebase that hands out missions, or you could lean to Bethesda and you find and get thrown into quests (like how in Fallout 1 you suddenly find yourself in a quest when just asking for information). Now, that can be kind of odd, but I also like what Final Fantasy Tactics A2 does, where you can easily go around the world but missions are how you battle. Take away the need to unlock areas first and the game could be quite open.
The really nice thing about FFTA2, FFX-2, BotW, Skyrim (and many Beth games) and others I can't think of right now is there is a blatant story to follow, but it's very open about it. In Skyrim and TA2, the main story is in effect the largest quest. The major story might end but the game doesn't. In X-2 and BotW, the story definitely has a beginning and end, but you can go about things however you want.
On the note of standard rpgs being "too stat reliant"; That's not necessarily a bad thing. One cool thing you can do in standard turn-based games is that you can set up enemies so that if you go to an area too high level for you, you only fight one enemy at a time (each encounter is effectively a boss or miniboss) but at the "right" level you start getting groups. Probably the most important stat to focus on here is Defense (and MDef if you use it). If defense straight decreases and can negate damage, level discrepancies can make things impossible, but if it instead lessens damage by a percent or something related (or defense doesn't or rarely exists), then you can always be capable of fighting something, regardless of level difference. For instance, in Pokemon, numbers are all multiplicative;
Damage = Level * (Move Power / 100) * (a.atk / b.def) * tiny random variance
Because of this, it's still possible to fight enemies upwards of 50% higher level than you, but you
have to know what you are doing (element systems helps a lot). As said above, Timed Hit systems and other ways to insert player skill over stats into battle can bridge the gap considerably. Also, the types of skills or states you can get can change things quite a bit; Haste doesn't make easy battles that much easier, but can bring tough enemies to your level (The Ant Queen in FFTA2 is probably the hardest boss in the game based on when you fight it, but it's... possible to cast Haste on your whole party to get on her level). Narrow but powerful enemies can allow tactics; Strong enemies in one area might use single target attacks, so finding ways to mitigate that (Taunt, Guard, Cover, etc) can let you fight something that at first blush seems impossible.
The other option that might seem odd at first could be to take what non-rpg open world games do and get rid of levels. BotW has sort of progression in hearts, but Stamina is almost more important to the game as a whole and damage and defense comes from gear. You could build your open world to be
capable of winning without gear and without traditional leveling, while still steering difficulty how you want and rewarding with gear and other bonuses to character power.
If you really want player skill to determine things, you could put all the focus on making battles into pseudo puzzles that have to be figured out (often what comes from high difficulty) to beat. Gear and other optional things can help, but you could just give the player a party and each member certain skills and subtly tell the player "You want to beat that enemy? Figure it out, you have the tools." kind of thing.