Weighting is painful to do using the brush. Its much easier to just assign the vertices to the proper vertex group and then edit the weights in the properties panel. At that point you have to balance the weights between each bone. Weighting is too complex to explain everything in a help post so your better off looking for some videos that show how its done if your still having issues.
There is a training video series called Humane Rigging by Nathan Vegdahl. You can buy a copy at the Blender store or if your broke/don’t want to spend the money you can probably find a copy on youtube somewhere since it was a CC release. He doesn’t really go into deformations in this video, but I remember at one point he shows you how to rig a hotdog using the above method. Unfortunately I don’t remember the exact part of the video that shows the method.
If you don’t mind spending the money, the video Massive Mammoth Master Class part 2 is a really good training video, and goes into pretty much everything you would need to make really nice deforms.