So it turns out the solution was pretty simple, but I'll cover the two cases I tried first for completeness.
Setting background-image on a QToolButton places the image on the button at the original size of the image. That is, it doesn't scale the image, nor does it resize when you resize the button. Using background-image did allow me to set the border that I wanted, however, so this was what I thought I had to do at first.
Setting border-image on a QToolButton places the image on the button at a scaled size to fit the button and it rescales when you resize the button. Unfortunately, this method overrides the border style I was trying to set.
Ultimately, the solution is to simply use image, not background-image or border-image. This gives me everything I want: an image that scales with the button and the border style I wanted.
My stylesheet is now:
border-radius: 4px;
border: 2px solid red;
image: url(myImage) 2 2 2 2 stretch stretch;
background-repeat: no-repeat;
background-color: rgb(100, 255, 100);
Edit: The caveat to using just image is that it will scale down if necessary, but not up. If your button is larger than your image, your image will not stretch to fit your button. Fortunately for me my image was larger than my button, so it scaled down. See: http://qt-project.org/doc/qt-4.8/stylesheet-reference.html#image-prop