An approach I have used in the past is including the optional `kid` header. The key id can be matched to the appropriate key needed to verify the signature. If you associate every user with a key, that means you can also delete any key and thus revoke the jwt of a particular user.

In this case obviously you have a persistence layer for the keys and can't claim to be absolutely stateless.

https://tools.ietf.org/html/rfc7515#section-4.1.4