Probably you should give up on compiling your function. The compiling system has limited type system. Lists have to be rectangular arrays of numbers of the same type (only Integer, Real or Complex; no Rational arrays), and so forth. Rules such as you have are not supported with the runtime system (the "Wolfram Virtual Machine" or WVM). Using non-supported types result in a call back to the main kernel for evaluation. Such call backs inside a loop are to be avoided, since it causes the code to run quite a bit slower, even slower than the uncompiled version. For the call back to function properly, you often have to declare the return type of the called, which must be one of the supported types. These call backs show up in the output of CompilePrint as a MainEvaluate call. Furthermore, some functions do not have a WVM version and also result in a call back. SubstitutionSystem is one of them. Your hope, I suppose, is that SubstitutionSystem runs as efficiently as possible already.

One slight improvement is to take advantage of the second argument of the Random* functions, and replace

Table[RandomInteger[{1, 0}], {3}, {3}, {3}]

with

RandomInteger[{1, 0}, {3, 3, 3}]

You can also use Nest instead of the while loop, but I expect that will save only a few microseconds. Compared to the time SubstitutionSystem will take, it isn't important in this example.

Finally, the uncompiled version of your function doesn't seem to work. I couldn't figure out what you wanted the output to be, so I cannot offer any suggestions about it.