For a new device (ie no existing files on it), wouldn't the simplest approach be to full block 1 (whether 512 or 4k bytes) with a series of "1"'s, block 2 with a series of "2"'s, (etc). ie incrementing the number that gets written as the block number being written to is written.
Reading that back (either the full device or a random sample) should pretty quickly identify whether things are still in their expected location.
Well, with the remaining trust available at this point you might just as well use something cryptographically secure, like encrypted ones, twos, or simple HMACs of the block number.
A too-simple scheme is likely to be detected (and bypassed!) by the firmware a nearly no time.
though I wouldn't expect this exact command sequence to work unless tee's buffer size divides /dev/DEVICE's capacity and tee errors out writing past the end of /dev/DEVICE before writing to stdout.
Reading that back (either the full device or a random sample) should pretty quickly identify whether things are still in their expected location.