If I am not wrong, to have control over both shutter and aperture, you have to go to full manual mode. Cos when you are in shutter mode, you can only control the shutter (and of course your lightning exposure, etc). The rest is automatic... as far as i know (I am a newbie too)
One thing to note is that if you pick a fast enough shutter speed in low enough lighting, the shutter priority mode may already be opening up the aperture as large as possible. If still under-exposed, the lighting is just too low for that shutter speed, aperture and sensitivity combination.
In such conditions, exposure compensation or even full manual control will not really help you.
If you do not wish to use the flash or decrease your shutter speed, your next option is to increase the ISO sensitivity (granted at the cost of more noise in your image).