Assuming the laws of physics are the same as in our universe, we just need to look at the conditions under which general relativity reduces to newtonian physics.
Since under "normal" circumstances (those we are used to) physics almost always behaves newtonian, it seems easier to list possible conditions for non-reducibility:
- relativistic relative speeds (v>0.1c)
- extreme gravity differences (relative accelerations of thousands of earth gravities)
- extreme energy densities (eg. the mass of the moon in the volume of an apple)
While such conditions will exist in many places in a normal universe, one that consisted solely of such extreme environments seems very unlikely. Since the significant distinction of non-newtonian environments is a high relative velocity/curvature, there would have to be no large (relative to the perception of the observer possibly concerned with newtonian approximation) region within which all relevant objects were moving slowly (<0.1c) and that had no significant curvature change.
One possibility to prevent regions with a consistent curvature from existing would be permanent gravitational disruptions - gravity waves - with a easily perceptible magnitude. However, I find it difficult to believe that life (as we know it) could exist (or develop) in a universe where all structures were permanently exposed to significant spatial fluctuations.
Another possibility would be a universe where almost all relative movements were close to the speed of light. While this seems even more problematic for the existence of life, a lower speed of light might not necessarily have a big impact on the cellular processes essential for life. Observers in such a universe would constantly experience relativistic effects, though information transfer would obviously be limited to a pace that would seem glacial to us.
Whether our kind of life would really be able to exist in such a universe (an extremely low speed of light would influence things like thermodynamics (movement of molecules), blood flow and nerve signal transmission) seems still doubtful, but such a universe would certainly be self-consistent and should allow for the development of observers (without observers, the question of whether a newtonian reduction can be locally useful seems to lose meaning).
If you are not at all interested in the existence of observers, a universe disturbed by high-frequency, high-amplitude gravity waves would also be consistent and globally non-newtonian (except on the smallest scales, where due to the laws of differential geometry every part of space seems flat).
If you want to have a universe where even on the smallest possible scales movement looks utterly non-newtonian, my only idea is to postulate a phenomenon generating gravity waves according to the Weierstrass Function. Since that function (and therefore the shape of the gravity waves) isn't differentiable anywhere, no region of space would look in any way newtonian.