Design question for a service that signs messages on behalf of a user
Store the key encrypted. Send the encrypted key to the user and have them decrypt it and sign the message. Whatever your objections are to this scheme, they are most likely either misguided or can be addressed by the implementation of the scheme.