Looking over your code, did you ever run it single-threaded to compare the performance? I see you spawning what appears to be a crapton of goroutines, each of which performs a very small number of operations, then terminates. As cheap as goroutines are, they still have some cost to startup and shutdown, and it's not a good idea to spawn a goroutine if it's going to do roughly the same order of work inside the goroutine as the spawn & shutdown costs. This is a pessimal situation. I'm not sure if you're seeing the GC fail or if you're seeing the scheduler choke under the harsh load.
If you just want nondeterminacy, I'd suggest using math/rand directly, not accidents of scheduling... which, as was just proved, can disappear as quickly as they appear. In fact it doesn't even take something as serious as a language upgrade for that to happen, that kind of indeterminancy can disappear if you so much as add a member to a struct or have another process on your system eating 100% of one CPU or something. It's not reliable, not even a little.
On my side I've experimented in the code a bunch with the number of goroutines as well as the number of different CPUs handling the requests, and although they seem to alter the nature of the image the program still produces output in a reasonable amount of time for most non-pathological values.
As to scheduling v. random functions, much of what I like about the original is that the scheduling is completely out of my hands and it's not guaranteed to be consistently distributed or reproducible. It's as though the computer were making its own decisions.
I have a project started to rewrite the whole thing in c++ using random and using entirely Manhattan distance estimations for speed, but working with C++ is incredibly unpleasant and difficult to justify when I need to find a real job.
If you just want nondeterminacy, I'd suggest using math/rand directly, not accidents of scheduling... which, as was just proved, can disappear as quickly as they appear. In fact it doesn't even take something as serious as a language upgrade for that to happen, that kind of indeterminancy can disappear if you so much as add a member to a struct or have another process on your system eating 100% of one CPU or something. It's not reliable, not even a little.