Conservation of energy can be derived from Lagrangian mechanics from the assumption that the Lagrangian is constant over time. That is equivalent to saying that the dynamics of the system do not change over time. If the mechanics are changing over time, it would certainly be more difficult to predict future states, and one could imagine the mechanics changing unpredictably over time, in which case future states could be unpredictable as well. But now we don't just have physics that changes in time, we have physics that changes randomly.

I think I find that thought more troubling than the lack of free will.

(I know of no reason why any further conservation laws would break in a universe such as that, so long as you maintain symmetry under translations, rotations, CPT, etc. Time-dependent Lagrangians are not exotic. For example, a physicist might construct a Lagrangian of a system and include a time-changing component that is determined by something outside of the system, like say a harmonic oscillator being driven by an external power source.)