Since you generate the user-specific keys, you can also keep a copy of these keys somewhere (somewhere safe, preferably) and use them when needed.
Alternatively, you can generate the keys with a cryptographic derivation system which uses a "superkey" and the user's identity. For instance, consider the following:
- The superkey is K.
- A user is identified by his name/login/email u.
- The key for user u is computed as: Ku = HMACK(u)
I.e. you use HMAC, using K as key, to compute the user-specific key. Since HMAC is deterministic, you can always do the same computation again, as long as you know the "superkey".
Of course, the "superkey" is sensitive; it must never be known to anybody else than the superadmin. In particular, you MUST NOT "hide" the superkey within some application code that goes to the user's machine. This can be a problem if the user key generation is supposed to happen on the user's machine (that is, it is done by "you" in the sense that it is "your application", but still on the user's computer or smartphone, thus within range of reverse engineering).
This HMAC-based mechanism is, really, a kind of efficient compression method for the same initial model, i.e. you keep a copy of the users' keys. (If that sentence seems obscure to you, then you don't know enough (yet) to securely deal with cryptography.)