Leveling characters through story telling

Realism

From a realism point of view, leveling up characters at random points in a story doesn't make much sense. Nobody just gains new abilities out of nowhere. You could argue all the combat and time spent to get to the next level counts as training, but strictly speaking you don't master new techniques without targeted exercise and training. Shooting a hundred fireballs at random enemies doesn't exactly teach you how to conjure food from thin air, for example. If you want to go for more realism, using story elements can make more sense.

As an example, consider the following: if your party is on a strange planet battling even stranger aliens, it wouldn't make a whole lot of sense the characters gain new abilities after beating a mini boss. Instead, it'd make more sense they receive training at their base after they return. Now, instead of simply stating they train, you could include a social encounter with a trainer, or a battle encounter with a particularly brutal drill sergeant, for example.

Training

Training can be more than just one time training sessions. Leveling up through training and story offers a whole range of opportunities for new characters. An excentric sage with endless, but peculiar wisdom might train a monk, a gun-for-hire low on cash might teach you a trick or two, a lifelong friend and teacher might be a recurring character and one you go to in times of need, and so on.

Training sessions can also strengthened the bonds with existing characters, including those in the party. New powers can lead to inflated egos or a broken confidence, if the players are willing to play their characters as such anyway, which in turn can lead to more intimate moments of getting a party member back on their feet.
New powers also leads to new combo possibilities. Training together can make the party more effective by using each other's powers in a synchronised fashion, something they would, realistically speaking, only be able to do properly after training.

If your players are into it, playing out training sessions can make a big difference in story setup. Consider the scene in the Matrix where Neo learns kung fu after having it uploaded into his mind. Playing out character training is the difference between "I know kung fu". "Show me". and "I know kung fu". "Excellent, time to move on.". The first has more build up and more character interactions, and thus more emotional investment.

NPCs

Using NPCs (Non-Player Characters) in training can also be more than just an excuse to include more fun characters once in a while. They can become heroes and villains in their own right. If a bigger threat faces not just the party, but the world as a whole, it'd make sense the trainers become part of the fight as well.
Trainers with a desire for power may try to seek the party member they train as an apprentice or accomplice in their desires. Or a party member who multi-classes into a different path might suddenly be seen as a threat who needs to be stopped. For example, an archmage might see it fit to try and stop a mage apprentice who started to learn more and more warlock skills on the side.

Discovering powers

Going to a trainer isn't always an option, sometimes the party might just be stuck in a dungeon somewhere without many options to improve, but leveling might still be necessary. Using discovery techniques could work well in these cases. Just as some classes in D&D have to focus on spells to learn them, your characters could focus for a short period during a quiet moment to discover themselves more.
This obviously doesn't work for everything, but it can make for a fun little interaction nonetheless. You could take it a step further and use discovery moments in combat. They're cliche in many tv shows, but they work in them, so why not in an RPG campaign?

Let's say a cleric has reached the threshold to level up, but they're still in a dangerous situation, so there's no time to train. During a difficult moment in combat, you could use the god they worship as a means to have them discover their new powers or perhaps grant them knowledge to figure things out.
A simple fighter might see a certain enemy make a useful combat move a few times, allowing them to learn from them in the middle of battle, and so on.

Leveling as a surprise

You could take everything even further. By asking your players for their character choices in advance, you can sprinkle in their new powers during the campaign. Their characters would grow more organically as they level, but without the choices being made entirely by them. This isn't for everybody of course, but it can be something to think about. It definitely requires good communications between the GM and players.
For example, player 1 might have a level 5 bard and told you they'll want to multi-spec into a rogue and a warrior in the future, and also gain more levels in bard. If the story so far has taken place in a city where they have to be cautious a lot, it would make sense to level them in rogue the next time they level. So as the story progresses, you can narrate them discovering new rogue abilities, and the player will know what's up.

Surprises like this are often very rewarding, it's part of what we love in video games, for example. It can help prevent things from becoming stale and simply a grind from level to level, but there are other ways to prevent this as well.
Surprises work great for character development too, but are best used sparingly. Discovering new things about yourself is often a fun and rewarding process, the same goes for our characters, but working hard to achieve a certain goal is incredibly rewarding too. Both can be mixed together as well. One character might train to become a better sniper, but during their training they might discover they have a talent for first aid as well.

Class dependent

How much you can do through training, surprises, discovery or other methods depends a lot on the classes you're dealing with, and also on the game system. For example, the wizard class in D&D can only use spells in their spellbook, so besides the 2 spells they gain whenever they level, other spells need to be bought, found or learned through other means before they can add them to their spellbook. This is a more natural progression already in place for this class, which forces your hand a little bit. At the same time, this makes it easier to apply similar methods to other classes.
Classes who will be more difficult to adapt are usually the ones without magic, as magic can solve anything. Still, with a little creativity it can be done, like my fighter example from earlier.

Obviously all of this is also very player and group dependent. Communication is always key at every point in the game, so make sure you establish some ground rules so everybody knows what to expect. It's all about having fun after all.