You seem to have drawn all the short straws 
Assuming you mean a PP3 type of 9v battery - they can't provide enough current for the Arduino except for a short period when they are brand new.
Going back to my theme of just trying one thing at a time --- power your Arduino from the PC USB connection until you have everything else working properly. Then if you switch to another power source you will know exactly where the problem lies.
A good question to ask yourself at every stage is "if this doesn't work how will I know why?"
...R