Arduino overheating with 5V addressable LED strip
The regulator on the Arduino is a linear regulator, which means that it reduces the voltage by throwing the rest of the power away. At 9V and 650mA, it's throwing away (9V - 5V) * 650mA = 2.6 watts. This is a decent amount of power, and more than the regulator can handle.

Using a switching regulator instead would cause it to make up for the drop in voltage by using less current from the source; a 90% efficient switching regulator would waste only about 5V * 650mA * 10% = 325mW, which is easier for larger packages to disperse.

Look on eBay or DX or the like for a 5V or adjustable DC-DC switching module. Connect the input to your 9V source and the output (set to 5V) to both the 5V input on the Arduino and the 5V input on the LED strip.