If all the PIC does is time 2 minute intervals you are wasting it's capabilities. You can do the same thing with a 555 timer.
As pointed out, the type of relay depends very much on the current it has to switch and the kind of load you are turning on and off.
I would use a 555 timer IC (very inexpensive) set as a 2 minute astable oscillator with near 50% duty ratio, feeding a bipolar power transistor (BD131 or similar) with the solenoid in it's collector side. The current will be fairly low at only about 0.2A so there is little point in making a more complicated driver circuit. A diode should be wired across the solenoid to trap back EMF and protect the transistor.
Total cost should be less than $1 US or about 60 rupees.