It would help if you can post a couple of pictures with the tire wedged at the brake shoes.
And what size and brand are the tires?
( click the Insert Image icon, click "basic uploader", then browse to the photos on your PC.)

Different pads might give you just enough clearance.

For instance, Kool Stop makes a low profile V brake pad. Kool Stop Thinline (Note that the long end of the pads are supposed to be toward the back of the rim, under the fork.)