I don't think it is necessary true.
More precisely: the Block Universe as an interpretation of classical, non-quantum special relativity is deterministic, because classical, non-quantum special relativity is itself deterministic. (So is classical, non-quantum general relativity, for that matter, so you could apply a Block Universe interpretation to any curved spacetime solution in GR.)
Imagine, for instance, that the world is a random set of points (events) on the spacetime manifold.
We're not allowed to just "imagine" anything we like in this discussion. We are only allowed to imagine things that are consistent with whatever laws of physics we are using. If we are using the laws of classical, non-quantum relativity, then we are only allowed to imagine scenarios that are deterministic--initial data on any spacelike hypersurface determines the entire spacetime.