The opcode testers I know assume from the start that a few instructions are 'known good' (say, 'compare to immediate', 'conditional jump' and a move or two) and work their way from there. As the tests proceed, the program logs the results to some output device so in case the program crashes you can have some good idea of where to start looking for the error.

That means you have to test manually at least those few bootstrapping opcodes, or rely on their implementation.

The idea is not only making sure that the opcodes work at all, but trying to catch subtle differences in the implementation as compared to some arbitrary baseline; that's what Zexall does for the Z80.

Maybe in an architecture as straightforward as the 8051, with much fewer dark corners than the Z80, something as paranoid as Zexall is not necessary. And yet, all those 8051 simulators and FPGA cores out there must have been validated somehow...