Scrambling the transmitted score is probably worthwhile.
To avoid cheat-engine type stuff, you can always scramble it in memory too. If you're storing seven variables, each of which, %10, is a digit, and you add a random number of 10s to each variable whenever a score changes, then it will be tricky to find a variable that matters. You could also get quite silly with that, by having certain values of the multiples-of-ten be illegal, and affect the score in "special ways", or send a signal to the server "this player is messing with the scores".
But most importantly, you should do what you said you cannot do, and send gameplay progress.
Sending every keystroke is not infeasible (MMOs do it!), but it would require storing a state machine of each game serverside. So, simplify.
So if it's, say, a platformer, then you have it send what level they are on, and a notification each time they kill a mob. You then validate that by saying, you know their weapon can kill at most 4 people, and fires once every second. Then if they claim to kill ten people at once, that's not legit. If they claim to kill more people than are on their current level, it's not legit. If the mob ids they send with their kill are from different rooms and could not be simultaneously killed, that's not legit.
Don't accept a score that's jumped infeasibly high in one go.
But, it's the internet, and lag happens, so you have to allow a certain flexibility in timing.
What if it's, say, a racing game? Well, you can give checkpoint timings. You know the car specs, you know its max speed, max acceleration, you know the min distances between checkpoints, so you can calculate the min possible time (allowing a little leeway for speeding up by getting hit from behind, powerups, etc).
So you avoid the "999999points" obvious hacks, and instead, they have to submit a while BUNCH of packets, saying "lap 1 done in [theoretical best time]", [wait a bit] "lap 2 done in [theoretical best time]", ... "end of race", "prize money spent on buying [upgrade] to improve theoretical best time"... improving each time.
Essentially: split the game down into gated waypoints, send what metadata you can validate serverside, and write logic that accepts or denies based on that.
This is a serious and hefty way to tackle the problem, and you should only do as much towards it as is worth. for a free online web game, just prevent the most obvious all-nines scores and be done with it. For a for-pay game, it's worth taking it further, depending on how core a game mechanic the leaderboards are.