I sounds like your motherboard isn't receiving enough power.
Try clearing your cmos (bios) first. Make sure that you have both power connectors on your board connected properly, especially the 4 pin. I would also double check you cpu cooler and make sure it seated correctly.
You also said that you put a fan on your video card. Make sure you have applied the thermal paste properly
There's also a troubleshooting guide in the motherboard form.
Heat is your enemy. You want as little as possible, but you certainly don't want to refridgerate your system either.
CPU Normal temp range is 30-40 degrees celcius
GPU (Non-SLI/Crossfire) normal temp range is 45-55 degrees celcius (expect a lot of discussion about this range, this is the range i'm used to seeing)
Also, if you know the GPU is a problem, why not replace it first, then test your system again. Alternatively, you can go through the troubleshooting guide (link in my signature) to see if there is anything else wrong in your set up.
In short, no, you don't need a 700w PSU to power up your particular CPU. In fact, I can't think of any CPU requiring a 700w PSU. That being said, when there is a potential power insufficiency concern, know that the wattage output isn't as important as the amperage output.
I suggest you go through the troubleshooting guide, if you haven't already. Also post the specs of your PSU, run MemTest86+ (download from memtest.org), and come back with the results.
Do a breadboard build. To accomplish this, remove everything from the motherboard, except for the the CPU and heatsink, and heatsink fan.
1. Place the mobo on a non-conductive surface (wood, cardboard, etc)
2. Connect the PSU and don't forget about the 4/8-pin connector near the CPU
3. If the board has a power button embedded to it, use that to power up your board. If not, use a flathead screwdriver to jump the power switch pins.
At this point your board should be trying to POST, but it won't because you don't have RAM installed. Did you hear series of beeps (1 long, followed by 2-3 short)?
If yes, proceed to step 4. If not, you may have another bad board.
4. Install RAM, one module at a time, testing for display. If your monitor shows a display after you've installed all RAM modules, you should see a POST error indicating that no hard drive (or no OS) is found. If you install RAM and the display stops showing, you may have a bad RAM slot on the mobo.
5. Reconnect your hard drive. If your mobo POSTs, then continue to add the rest of your devices one at a time until either all are connected and your mobo still POSTs, or until you've added something and your mobo doesn't POST. Should the latter happen, remove the last connected device and try again.
6. If everything is connected and working (mobo POSTs) outside of the case, you likely have a short. If you have a short, remove and reinstall all brass standoffs. Now remove everything from the mobo, except for CPU, heatsink, and heatsink fan. Reinstall mobo to case, and follow steps 1-5 again.