Is this actually a dependency cycle?
This is one of the key reasons for the dependency graph rewrite, the old blender dependency graph treats an armature as a single node in the graph, dependent on everything any of the bones are dependent on. 

The new depsgraph, which is still a bit of a work in progress, should fix this.
It can be enabled by passing --enable-new-depsgraph when launching blender, and may help.

For more info see:

https://code.blender.org/2015/02/blender-dependency-graph-branch-for-users/
https://code.blender.org/2015/03/more-dependency-graph-tricks/

A separate armature would fix this for now as well.