One game that comes to mind is Super Meat Boy (SMB). SMB doesn't really have a tutorial, but the first few levels act like one. The player has to perform certain mechanics to complete the level, and these mechanics are emphasized by the level's design. Want to teach the player about long jumping? Give them a big hole where the only way across is a long jump. Want to teach them about wall sliding? Give them a level where most of the level involves wall sliding in order to complete it.
Keep in mind these levels are also accompanied with little tutorial popups that show what the desired action is, and how the player can perform it. The biggest thing to pull from these is that it doesn't pause gameplay and there isn't any text description of the tutorial. Pausing gameplay to teach the player something that they may or may not know kills the pace of the level. If they are seasoned, they will already know, and if they are not, then having a video demonstration, not a lecture, will provide the clearest and most player empowering way of teaching them.
Another game that I've seen do this well is Volgarr (disclaimer: I haven't played the game, but have seen a little bit of gameplay). Volgarr, if memory serves, doesn't have a tutorial, but similar to SMB, has obstacles at the beginning levels that require you to perform certain game mechanics. The interesting thing about Volgarr was that it didn't prompt the player with how to do it, but only presented the obstacle. It was up to the player to discover the solution, via pressing buttons.
These examples worked in their respective games, but keep in mind that context is key. They might have worked for one game, but it might not work for yours. Keep the theme of the game in mind, as well as the context of the situation.
