So, would it be possible to verify that an entity is a full node if they sign to show their address and provide a hash of the entire blockchain + a nonce?
Can a contract be written into the scrypt stating that a designated node can receive the coins of a transaction? Or, why not give higher priority to transactions that include a small transaction to a known node address?
If an alt protocol is created to reward nodes, then it may be better to abandon processor-based mining altogether. It is possible to devise a protocol in which nodes constantly send blocks, and send 'gibberish' transactions in the block to provide the randomized value that allow the hash to be different for each block. When some set of conditions is met (like Node A can prove to the network that it received a transaction from Node B and they each used the same salt/random value to generate the transaction), then a reward can be split among nodes A, B, and all other nodes that directly observed and confirmed that transaction. This system could feasibly work because it's intention is to consume bandwidth - so needing tons of bandwidth to inform and validate with the network is a good thing, rather than a bad thing.
The benefit of consuming bandwidth rather than ASIC cycles is primarily that, in order to 'mine' faster, the miner must increase their bandwidth, which allows them to transmit more transactions. There is a perfect correlation between helping the network and the miner's profit. The gibberish transactions sent along the network can be discarded shortly after they are received; there is no reason to keep them, they can be treated just like any failed attempt to mine a block.
The actual signal that a block has been mined may be a bit tough to figure out though - the specific example I gave would be too easy to exploit.