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?
Yes. You have to import the keys into a client like Electrum. Else, you can download the brainwallet script and only use the sign feature
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)
The sign message feature will not reveal anything about your Bitcoins private key if it is done correctly. I've never heard of any client leaking the private key. You wouldn't have any problems if you could verify that the Electrum build is official.
c) Do I need to pay fees to submit the message?
No. The message is not transferred over the blockchain. You have to manually send the whole output of the message for users to verify it.