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?