Non-deterministic processors are generally sold as a method to vary processor timing and power. To my knowledge they are theoretical as synchronous systems, as I have never seen any literature where one has actually been constructed. The premise is that if you have varying instruction order, and completion time, you then have some level of robustness to side-channel attacks. It is important to note that these are still synchronous systems. The closest work that I know to this where hardware exists was body of probabilistic computing work by Palem, George and Marr.
You could easily make a non-deterministic system with asynchronous logic. When I make asynchronous systems, creating noise is trivial because of the completion trees, and I do add random noise to the completion logic to slow it down as a verification of robustness against EMI. This method would make the circuits robust to a side-channel attack due to random completion times for all logic. Having said that, the dual-rail encoding of asynchronous circuits means that you cannot have a power attack, but only a timing attack. You could size the completion trees so that they always required the same time; however, that would eliminate the speed gains of the asynchronous circuits.