Is there any way to hire someone to generate a sufficiently small hash of a value + nonce, without knowing value nor nonce? Suppose I have a 128-bit value X, and I want a keccak_256(X || nonce) sufficiently small to require a lot of work. Is there any simple/obvious way (possibly interactive) way to hire someone to find me such a nonce, in a way that he doesn't learn about X, and that he doesn't even know what nonce he produced?

I can't fit that particular problem on what zkSnarks seem to enable one to do.
Here's the obvious answer that avoids multiparty computation (which tends to be expensive):


Given your $X$, select a random value $N1$, which would be 256 bytes long for keccak_256 and 48 bytes long for SHA-256, and compute the intermediate hash state of $Hash(X || N1)$.


If your hash function is SHA-256, this is an intermediate hash of 64 bytes (1 SHA-256 block), which requires a single hash compression function evaluation (yielding a 256 bit intermediate state)
If your hash function is keccak_256, this is an intermediate hash of 272 bytes (2 Keccak-256 blocks), which requires two permutation evaluations (yielding a 1600 bit intermediate state).  We use two permutations for Keccak because the permutation function is invertible, and so if we used only a single block, the hireling could invert the permutation and recover $X$ and $N1$

We give the intermediate hash state to your hireling, who searches fir an N2 such that Hash(X || N1|| N2) is a small value; he can do this because both hash functions can be expressed as functions of the intermediate state and the rest of the message.
Once he has found such an N2, he sends it back to you. This gives you the value $nonce = N1 || N2$ you're looking for.


This solves the issue; the hireling cannot convert the hash state back into $X$, and since he does not know the value of $N1$, he doesn't know the full value of none.