The first thing I obviously did was googled for possible solution. Unfortunately the solutions were not what I needed, so I decided to try the problem myself. Luckily there are two methods that are of help in CheckboxTreeViewer: setGrayed and setChecked, setGrayed nicely grays out checkbox so the user knows that this checkbox is disabled.

The disable mechanism revolves around value in model's isEnabled field. My model is roughly based on example from this article, but any model will do as long as there is variable that sets a particular model element not enabled. Screen shot on the left shows how this code works in my application.
Eclipse 3.5 has interface ICheckStateProvider that pretty much does what I wanted to do here. However, I am currently at Eclipse 3.4, so will have to wait for this once I move to 3.5.