Which, in your opinion, is the best AMD CPU for gaming?
I'm on a budget so Intel (sadly) isn't an option;unless I choose something like the Q8300 or the E series. I could afford the 955 and anything below for AMD. I've heard about the AMD's CPU heat problems but I'll still be using the standard cooler.
Should I opt for a Intel CPU with less clock speed but better performance?
Well AMD's are just as good at gaming - if not better - than intels.
The 955 is a solid choice but more important is the graphics card. You would be a lot better off with say a X3 720 BE and a 5770 gpu than say an X4 955 BE and a 8800gt for example. How much are you looking to spend overall?
Your current system, or what else you plan to purchase (as well as the budget as suggested by Jenny) would be most helpful. Phenom II CPUs run quite cool, it's the original Phenoms that you want to avoid (9950 etc) as they were woeful.
Contrary to popular belief, Gaming in it's current state is primarily driven by GPU performance. And as long as the CPU is "good enough", there is little difference in most titles. The caveat being that a better/faster processor now will be more likely to provide that adequate performance for a longer period of time as more stressful games are developed and released.
Coolit's choices above are solid, and worth further investigation. From that point, if passing over the 955 for a 720 in order to save money makes the difference between one video card and a superior one, then definitely put the money into graphics.