The second law will always be true in any universe that shares your concept of time, because your concept of evolution is essentially just an interpretation of the thermodynamic temporal arrow in a somewhat tautological fashion.

If you had to simulate such a universe in a computer program, how would you do it? What would it look like?

Perhaps instead of Brownian motion you'd have something more directed. Scientists inhabiting the universe would observe a "force" that brings elements of like kind together into nice orderly structures instead of random soups. It would be as if time ran in reverse. Perhaps instead of a big bang, the initial state would be a flat universe with just the minutest of perturbations in the energy gradient that would gradually evolve into a state of maximum order.

In order for it to be useful/predictive, you need the microscopic dynamics to preserve phase-space area, which is actually pretty special. I think you're also going to need something like ergodicity for "generic" systems.