If you use 4 AA rechargeable batteries then you will not need a regulator, nominal voltage is 1.2 volts each. But the PIC you are using will run on 2 volts with the 8 Mhz OSC...

So... Use any AA battery pack with a LM317 voltage regulator set to run at ~3.6 volts for the PIC. You will need three 470 ohm resistors to set the regulator. Then you should be able to fire the transistor that is triggering your relay from the PIC.

http://www.national.com/mpf/LM/LM317.html#Overview

The PICKIT2 has an "auto detect" setting for the voltage. if there is voltage on the PIC the PICKIT will deal with it. No switch needed.