2 parts to my answer: one actually addressing the question and one suggesting the question needs questioned.
One idea that springs to mind is holding regular 'blind level contests'.
The general premise is that you have a separate score board only for these contests where by once a month the newest contest level is made available and players update their game to install it. Scores for this level can then only be submitted for N amount of time after the update, say 30 min - 1 hr depending how complex the game is.
You could take this a step further and have multiple level releases throughout the day, some sort of aggregated scoring at the end.
It goes without saying this depends greatly on the business model of the game and whether it will have regular updates / releases or whether it is meant to be fairly static as in released and forgotten about. However this style of contents should allow your core players who will care about how they compare to others to take part and find out.
Is looking up the solution online really cheating?
If I want to be the best at something, say Mario Kart, then I'm going to do all the research I can to find out everything I can about the game so that I am the best. If I put in the effort to find out the shortest routes, the quickest characters, the best items and so on and use this knowledge to beat all others then why am I a cheat just because I didn't work it out myself?
To take it back to your game consider Portal, a level based puzzle game. If I want to be the fastest at it then it is just common sense to see what the current fastest player is doing and try an improve on it. I wouldn't say this is cheating.
You see further standing on the shoulders of giants after all.