Any eth*/web3 wallet that supports NFT's (and thus supports arbitrary 'web sourced' transactions, such as the approve() message and the transfer() methods) supports signing messages. eg: metamask. This is a non issue for the NFT holders. The https://github.com/walletlink/walletlink standard appears to be what a lot of 'stand alone' type wallets are using for this compatibility.

If the client doesn't support arbitrary transactions (eg: it is a 'receive and spend ether' only type wallet), its probably not interacting with NFT contracts in the first place.