Is it possible to sign a message/transaction, then have another wallet execute the signed message/transaction without first calling "Approve"?
This question is for both ERC20 and ETH.
What do you mean by "have another wallet execute". After you sign a transaction you don't need wallets anymore. You need a valid node that will post your transaction. Usually wallets have access to network nodes so you don't need to worry about accessing the network after signing the transaction.
If you are referring to a wallet in terms of everything but a contract - in that case, the answer is no. But you can create your own "vault" contract, where you can deposit your funds and add a function (callable only by an address that you specify) to do something that you want.