I tried this game again and the issue is still present.
Tested with 3.12 and recent mesa (head:
f0f202e6b764be803470e27cba9102f14361ae22).

However, with a current apitrace it's now possible to trace and replay it on
r600g to provoke the GPU reset. Using past apitraces makes the game work
without traces/glitches.
I'm using apitrace head 0227203a229e85f98a491c6b9480c0bc210f1dbb, I didn't test
if a replay with older versions yields the hang.

I've uploaded a trace here (~260MiB):
http://static.hackmii.com/dhewg/brutalz.trace.xz

Replaying that without R600_HYPERZ reliably reproduces GPU hangs on my BARTS
card. Replaying it with R600_HYPERZ=0 makes the hangs go away, but you'll see
glitches on the hero's face (effects like described above).

Note: Trace is 1920x1200 fullscreen. Windowed mode or different resolutions
didn't always lockup. I tried to trim the trace down, but apitrace choked on
it.