Measuring non-planar objects in image
I would go for option a combined approach, which requires a stereo setup:

First of all, 3D depth information (which you would use as an additional cue) can be obtained through a stereo matching method. Depth images mean that you end up with 3D surfaces. At this point you could use a surface matching algorithm to initialize the positions of these objects (or cubes). I have implemented such an algorithm in OpenCV. You could find this here.

Luckily, for a calibrated stereo setup, you will have the intensity images and can use those as well. By now, you have the initial poses of the cubes and you would like to refine them. I would then suggest that you use a projective version of the ICP (iterative closest point) algorithm to obtain the most accurate fitting, to the image edges. Again, you could use both cameras in your error function (which you minimize) to reduce noise.

Note that, the stereo images may suffer from extrinsic calibration errors, as well as measurement errors, decreasing the overall accuracy. That's why you use it to initialize. For cases which do not necessitate accuracy you could stop at this point. If your conditions are as strict as you mention, then simply, the monocular/edge based techniques (the second stage, I described) will provide you a better result.