One very common mechanism is getting stars or medals for level completion - 3 stars or gold medal for the best solution (or time below X etc), 2 with a worse one and 1 star for something that barely qualifies as solving it. Then people can repeat as many times as needed to get the desired number of stars, while 1 star solution is usually fairly easy and unlikely to make someone hopelessly stuck. This is often paired with "get X stars to unlock level Y or world Z".

Another somewhat less common thing is that on N-th try you get extra powers to have it easier to complete the level, or difficulty gets down slightly or something similar. Usually you don't get the choice and receive the power boost, other times you get an option to keep struggling or make it easy. This is viable when you want to demand the "proper" solution for all levels, yet allow players to progress when hopelessly stuck to avoid them quitting.

The obvious disadvantage of both is that both options are only useful for problems with (reasonable) degrees of solution. Many puzzles require "aha" moment. Take the well-known problem of connecting 3x3 points with 4 straight line segments as an example - connecting 8 points or using 5 segments is trivial and pointless. In that case I would rather let player simply skip the level.

Here’s my contribution. These are methods I’ve seen used. I do not necessarily like some of these methods either for my games or in the abstract, but for completeness I think it’s worth listing them.

If you know of another I haven’t listed here or have your own unique idea for something, please do post it as another answer to this question.

A “wider lock”

Instead of having level 1 available to the player when starting the game, they have access to all of level 1 through level 5.

N, the total number of levels that they have completed up to that point, is tracked. At any point, the player has access to all the levels from 1 to 5+N.

For example, if the player beats level 1, they then get access to level 6. They then might get stuck on level 2. That’s fine, they can go to level 3, and if they beat that, then level 7 unlocks.

Advantages:

• The bottleneck is now much wider. The player needs to get stuck on 5 (or however many you decide to let them start with) levels before they can’t progress any further.
• The difficulty curve of the game is still roughly maintained, since the player can’t skip over too many levels at a time.

Disadvantages:

• The player can still skip over certain levels which you may really want them to play. If you introduce a feature on level X, you probably want to use it a bit on level X+1 in a way that is more complicated. The player may get confused on level X+1 not knowing what that feature is. Also, if they’re skipping level X because they find the feature hard, they’re likely to find level X+1 just as hard.

Parallel sequences of levels

Instead of having level 1, level 2, etc. you now have several different linear sequences of levels. You have level 1-A, level 2-A, and so on, as well as level 1-B, level 2-B and so on. Beating a level in a certain sequence unlocks the next in the sequence. Each sequence is probably called something like a different “world” and is themed differently or something like that.

Advantages:

• The bottleneck is now as wide as how many sequences of levels you have.

• You can maintain a difficulty curve and tutor players on features within each sequence.

Disadvantages:

• Much less control over the overall difficulty curve, compared to either the original system or the “wider lock” solution.

• If you want to reuse the same game features in each sequence of levels, you might want to re-tutor the player on how to use them in each sequence, as to make sure they understand it no matter which order they played the subsequences in. This can feel boring and repetitive to the player. This could be slightly mitigated if there is some relation in-between the sequences, e.g. if level 1-B unlocked after the completion of 5-A. The player then has 6-A and 1-B at their disposal, and hopefully the levels 1-A through 5-A are easy enough that someone getting stuck on them is extremely unlikely.

Can pay to unlock levels via in game currency (or even real money)

Perhaps the player collects some in game currency of some sort throughout the game. If they’re stuck on level 6, then they can unlock it using 10 coins. Perhaps an in-app purchase could also be used to unlock all levels.

Advantages:

• If using in-game currency: The player now has two ways of getting to level 6: beat level 5, or use 10 coins. Perhaps these methods could correspond to two different skills, which could reward more diverse playing styles.
• If using real money: You get paid. The player can get rid of the barrier if they get stuck for a small fee.

Disadvantages:

• Either: The player can still skip over the tutorial levels you want them to play.

• If using in-game currency: Perhaps the player struggles both with beating level 5 and getting 10 coins.

• If using in-game currency: Stingy players. Too-awesome-to-use syndrome is a thing, some people may deliberately not use the coins in case they’d want to use them later for something else, whether that’s for unlocking another level (“level 6 will be even harder, so I want to buy level 7 instead!”) or some other feature.

• If using real currency: The game is now pay-to-win, and less accessible to poorer people.

• If using real currency: Someone who is willing to pay for all levels is likely to eventually get round to beating all or most of them. Eventually the purchase will have no further effect on the game.

• If using real currency: There’s a lot more hassle in developing the game as you deal with all the effects of having in-app purchases (practically getting them to work in the code, dealing with financial/legal stuff)

Branching

You can have alternates of level 1 equivalent. For instance: A1, B1, C1. Progressing past through any level 1 unlocks all branches of level 2.

The mechanic or challenge introduced in each level may be the same or similar, or different altogether.

Example:

1. Mario-like game. After playing introductory level 1, you can pick path A2 (forest), B2 (hills), or C2 (beach). Each has 4 levels (A2-4, B2-4, C2-4) which then later converge into level 5. Later on it might branch again.

2. Crying Suns. Each round has 6 stages (CMIIW, I haven't played for a while). From your starting node, you can pick up to three nodes (1A, 1B, 1C) as your first node. Then you progress by selecting the next node (2A, 2B, 2C) again until you reached the round's jump gate.

3. Avatar-like game. You supposedly have to master fire, water, air, and earth. You can however choose to pick your first element, until you finish mastering all four. By selecting an element, you can play levels associated with that element. These levels might be sequential (fire-1, 2, 3, and so on), or unlocked all at once.

The player getting stuck on a level is usually not a problem with that particular level, but rather with the levels that came before. Their job was to prepare the player for the challenge. Teach them the required knowledge and skills and reinforce them so the player can overcome this more advanced challenge. They failed to do that, so now the player is stuck. So the solution is to improve the teaching effect of the levels before. Or maybe add some additional levels in between that reinforce the skills the levels taught by presenting a similar but easier challenge in an easier to understand context.

Doing some rigorous playtesting with many different people will usually help to identify such points in the level progression.

But even the best playtesting might not account for all players. So as a fallback mechanism you could add some affordances and motivation to return to previous levels. That way a player who gets stuck on level 12 might get encouraged to replay levels 9, 10 and 11 and thus pick up the knowledge they missed but need to beat level 12.

For me, the best answer is to not lock levels. Clearly mark tutorial levels. Clearly mark the difficulty of levels. Clearly explain to the player when there is a narrative reason for completing the levels in order. Then leave it up to the player to decide how they want to play.