How can I make backtracking interesting?

One thing I liked about the backtracking in Super Metroid is how your new powers allowed you to get through the areas faster, but in a more challenging way. Another way is to place items such as health upgrades (or obvious switches/breakable blocks) in plain sight but out of reach until you come back in possession of another item.

A different game that makes backtracking interesting is Dark Souls. The difference with Dark Souls of course is that you aren't usually locked off from areas, it's simply that the enemies are too high-level and thus will be hard to kill. When you first come to Anor Londo, there are a bunch of Sentinels standing around that don't get easily aggro'd, although some guard chests. At that point, most players won't be able to really take them on, so they are ignored. When you come back to go to the Duke's Archives, you can take on the Sentinels and claim the treasure. The same goes for Blighttown when you need to go to the Demon Ruins: it becomes much easier to explore the rest of the swampy area and you can find the Great Hollow.

You said that modifying the level beyond recognition is out of the question, but what about only small, randomized modifications to levels?

This can be in form of events which only have a certain chance of happening whenever the player traverses the area. When there are multiple such events which also interact with each other, it will result in a slightly different experience everytime the player passes through the area.

One game which does this with an interesting effect is The Stanley Parable. The gameplay of this game is based on lots and lots of branching paths, and after trying one path through the game, the game resets and the player can make different choices and see what happens. That means that the starting area of the game is traversed many, many times. To make this a more interesting experience (and to confuse the player even more), this starting area has a certain probability to have some random but meaningless changes. Corridors change their length, sections are added, removed or replaced, or rooms suddenly have papers all over them.

Such completely unexpected and unexplainable changes would of course not work in a game which isn't as abstract, meta-referential and intentionally confusing as TSP, but there are other, more plausible things you can have to make your game world feel more alive.

In a hostile area, you could have enemies which only spawn with a certain probability or have different positions in which they can spawn. That way the combat experience will be a bit different each time the player passes through the area.

In a friendly area, you could have background events happen or not happen with a certain probability or spawn NPCs which approach the player with a certain probability during each pass-through and say something which might or might not be important.

What you are talking about is not easy to do.

If you are going to send the player back through an area then you can still make a lot more game experience there by making new things happen on their journey back. Consider the original Halo where the second half of the game was effectively a fight back through the locations of the first half, but confronted by new enemies. This approach makes effective reuse of the environments but it was not without it's critics in Halo and doing it well is certainly difficult. You should be able to up the difficulty on the return journey so that players benefit from knowing the terrain somewhat. On a two-way trip you could also make certain rooms and power ups available on the way back that were not available on the first journey true, as mentioned in other answers.

If you are thinking of having more of a sandbox setting, then giving the players ways of jumping to the general area they are aiming for is helpful- the various Zelda games do this in fairly useful ways, giving the player a horse or a bird for faster travel at a certain point. You still move through the same areas often, but you can at least get to them quickly. The Elder Scrolls games do something similar with Fast Travel, allowing you to quickly return to a location you have previously visited. In both cases dropping you in the right area does not stop you from having to revisit places you previously passed through once you get there, so the content is re-used effectively.