What challenge should I use in a challenge-response proof-of-work?
A good PRNG can't be exhausted, so your argument against random bytes doesn't matter.


  firstly I'd like the server to be completely stateless. 


Sounds impossible to me.


a PRNG needs state. A clock needs state.
An open connection is state too
You probably want to store open challenges too. This part isn't strictly necessary, but very convenient.




You might also want to include something unique to the server in the challenge(for example its domain or IP address) so clients can't be tricked by one server into solving the challenge for another.

I'd go with the server sending 16 random bytes as challenge, and the client responding with something like ServerIP || HMAC(proof, Challenge || ServerID)