Minecraft Java Edition – How to Easily Find Structures in Minecraft?

Yes, the Nether is generated the same way as other terrain (in fact it's just a special biome). It uses your world seed to generate it, so re-generating will not affect the layout of it (although there may be slight changes, such as the position of mushrooms, but I'm guessing that this doesn't bother you too much).

So here's an idea (and I haven't tested it yet, but hear me out): you put a minecart on a line of powered rails with some power source on them all (nearby redstone blocks, torches, whatever). This rail travels past all your locations. When you want to get to a certain place, you use a command block with /setblock to replace the powered rail at your desired location with a solid block, and the one in front of it with an unpowered rail. Then push your cart--you'll continue down the rail until you hit the new wall and stop when you get to your destination. To reset it, you can just fill the rail row with powered rails again (using the replace parameter to only replace unpowered rails and your stopping block, for safety); then push the cart back to the start (which, by the way, the first rail should have no constant power source and only be powered when you want to access something).

Or, if you want an auto-reset, you could even use setblock to spawn a command block above your stopping block which tests for the presence of a nearby cart, run that into AND gate with another (always-present) block which tests for the presence of a nearby player and inverts that, and when the output turns on, run the reset circuit (which would /tp the cart to the beginning again, fill the track up with powered rails, and clear out the new command block).

Maybe there's a more efficient way of doing this, but I think it should at least work.