The FX-8350@4.6ghz should manage that set of FPS goals in 99% of conditions/games. The only time it would drip below 40FPS would be something like a WoW RAID or major town, though even overclocked haswells will dip to ~30-35FPS in those conditions (expect as low as 20-25FPS on the FX-8350).
An Athlon X4 860K @ 4.6GHZ could actually achieve similar results in gaming workloads. In fact, in many games it would do even a little better, while dissipating significantly less power. This would cut your PSU requirements down by maybe $20-40, and cut the cost of the heat-sink and fans to accommodate the overclock by about half, and cut the cost of the motherboard by $30 or more. You could then apply the savings towards an improved GPU, which would allow you to maintain those high settings (or better) in todays games and more future games without dipping below your FPS goals, and if possible, switch that to an Nvidia GPU to further improve FPS minimums in DX11 games. (The Nvidia drivers split the compute workload in DX11 titles up across multiple threads better, which can improve performance by up to ~20% in compute intensive games, which can help compensate for the lack of a stronger CPU like an i5.)
----------
PCPartPicker part list /
Price breakdown by merchant
CPU: AMD Athlon X4 860K 3.7GHz Quad-Core OEM/Tray Processor ($82.94 @ SuperBiiz)
CPU Cooler: Zalman CNPS9900MAX-R CPU Cooler ($43.06 @ Amazon)
Motherboard: MSI A88XM GAMING Micro ATX FM2+ Motherboard ($94.99 @ Amazon)
Memory: Mushkin Redline 8GB (2 x 4GB) DDR3-1866 Memory ($82.99 @ Newegg)
Storage: Western Digital Caviar Blue 1TB 3.5" 7200RPM Internal Hard Drive ($54.99 @ Amazon)
Video Card: EVGA GeForce GTX 970 4GB Superclocked ACX 2.0 Video Card ($348.99 @ SuperBiiz)
Case: Cooler Master N200 MicroATX Mid Tower Case ($44.99 @ NCIX US)
Power Supply: SeaSonic G 550W 80+ Gold Certified Semi-Modular ATX Power Supply ($74.99 @ Amazon)
Total: $827.94
Prices include shipping, taxes, and discounts when available
Generated by PCPartPicker 2014-11-01 23:59 EDT-0400
For $800, if you want an AMD CPU in your build, the above is better for gaming than the FX-8350+R9 270X. The CPU will be +/-15% the performance of the FX-8350 in gaming workloads when clocked the same, but the advantages of nvidias driver for DX11 games is really what will help bridge the gap between the 860K and a more expensive CPU. In fact, at 4.6ghz, the 860K running a DX11 game on an nvidia GPU, will perform as well or better than a more expensive locked i5 haswell paired with an AMD GPU in many cases.
When clocked the same, the FX-8350 doesn't begin to outperform the 860K until the workload can saturate 6 or more of its cores. Real-time workloads like games rarely present this way. As such, in the limited cases that they do, the performance advantage of the FX-8350 would be very narrow (never more than ~10-20%). In most games, which produce workloads that only scale to 3-4 cores, the 860K will actually pretty consistently be the stronger performer. Given the huge discrepancy in price, I would take the 860K for gaming long before the FX-8350.
FYI: I own an FX-8350, and know what it takes to run it at 4.6ghz and how it performs... if you'd like me to take a picture of the power meter on this thing running prime95 at 4.6ghz just let me know, you may be in for a shock.