This is not a trivial problem. As you said, it is easy to make levels when the aim is to teach the mechanics but it is really hard once that is done. The way that we did it for our Android puzzle game 'Masters of Light' (link provided for convenience if you are interested) was to have one person design the level on paper and give it to somebody else to check over then make it and play test it. We increased the difficulty by putting down a list of skills that they player needed to master in order to finish that level. If the player had those skills then they should be able to finish the level.

And that was the trick, we simply required the gamer to apply more skills and tricks that they should have learned the harder the level got.

I should also mention that it is not an easy road, most puzzles have to be hand made. The two of us made 49 levels in total and it took us two and a bit months working on it nearly full time. And that was just to design the levels conceptually on paper, it took a few more weeks to put the levels in the game itself.

N.B. I too would recommend the Evaluating Game Mechanics For Depth Article linked here.