How to check a signature on an arbitrary message? I'm looking to have a p2sh transaction that inside the redeem script there is OP_CHECKSIG (or any other op-code) that verifies a signature on an arbitrary message (not a transaction). 
I have been looking, but all I could find is that OP_CHECKSIG only verifies signatures on transaction. I need a signature verification that I'm able to give the message (hash of message) to the verification procedure. 
Something similar to ecrecover that takes in a signature, verificationKey and the message. Is this even possible using the existing op-codes?
No, this is not possible. There are no opcodes that allow you to check a signature on an arbitrary message.