I have a paper wallet, and would like to sign a message (NOT a transaction!) offline, on an air-gapped computer, transfer the message and signature using a USB key to an online computer and send the message and signature online.
a) Is there a way to achieve the above?
b) Do I put my private keys in danger in any way? In particular, can I trust the digital signature algorithm to be robust? (i.e. NOT to reveal anything about the private key)
c) Do I need to pay fees to submit the message?
question was already answered by the other guy above. Besides Electrum you can use mycelium in mobile. Importing the privatekey is safe as long as you are sure that you device does not have any key stealing virus or malware in it. Signing and verifyjng the message is also free so no fee.