Hmmm... yes, totally freely randomly won't work. All right. If I can go classical I can do it.
You have some ensemble of particles and each pair maintains a stack recording a partial history of their interactions, kept in terms of distance of separation (with the bottom of the stack being at infinite separation). Whenever two particles approach each other, they push the force they experienced as they approached onto the pair's stack; the derivative of this force is subject to random fluctuations. When two particles recede, they pop the force off the stack. In this way, you have potential energy (the integral from infinity to the current separation over the stack between two particles) as well as kinetic, and it is conserved.
The only parts that change are the parts of the potential that aren't involved in interactions at the moment.
Of course, that won't work in a quantum world since everything's overlapping all the time. But you didn't specify that.
EDITED TO ADD: there's no such thing as potential energy if the forces can only act to deflect (cannot produce changes in speed), so I could have done it that way too. In that case we can keep quantum mechanics but we lose relativity.
I still don't think you're conserving energy. Start with two particles far apart and approaching each other at some speed; define this state as the zero energy. Let them approach each other, slowing down all the while, and eventually heading back out. When they reach their initial separation, they have kinetic energy from two sources: One source is popping back the forces they experienced during their approach, the other is the forces they experienced as they separated. Since they are at their initial separation again, the stack is empty, so there is zero ...
This is a thread where people can ask questions that they would ordinarily feel embarrassed for not knowing the answer to. The previous thread is at close to 500 comments.