Ortlieb makes a messenger backpack too - its *huge*, I could probably get inside and close it up huge, but its totally waterproof and probably bombproof too.
I have issues with one shoulder, so funny enough I prefer only have a strap on the good one. I do find, much like with the waist strap on a backpack, that properly positioned the chest strap on my messenger bag takes most of the weight off of my shoulder too, so its actually pretty comfy to ride with.