Something you have to understand is it doesn't matter how many cores a CPU has but how powerful they are (IPC - instructions per clock per core). The latest Intel CPU's have approximately twice the IPC per core as the AMD price point equivalents at relative clock speeds. In gaming at stock clocks, that G3258 will actually out perform the A8 quad-core in most games. Not by much, but it will.
Clock speed is only relevant/comparable within the particular family of CPUs, example; within the Pentium G-series CPUs from Intel. A G3420 will be a little faster than a G3220 because it's clocked higher. But the clock speed of say, the A8 from AMD cannot be compared the same with the clock speed of the Intel G series because their architectures are very different. The fact that a G3258 at 3.2GHz will perform as good as or better than an A8 at 3.9GHz shows you why you can't judge by clock speeds between Intel and AMD, alone.
Also, you said you had a previous build with a G3220 and claim it was slow. Did you happen to have a mechanical HDD in that build? Too many people mistake a slow HDD for a slow CPU because they don't realize the HDD is the biggest and slowest system bottleneck. Install an SSD and that same system will run WAY faster, regardless of the CPU. If you're running a mechanical HDD, it doesn't matter if you have a G3220 or core i7, you still have to wait for that HDD to retrieve the requested data.
The GPU I suggested, the R9-270 performs WAY better than the 750/Ti. In fact the R9-270X is almost equal to the GTX 760. Unfortunately, right now there is no decent GPU from Nvidia that bridges the gap between the 750ti and the 760, but AMD has several options that offer great performance and really good prices. The 270 being one of the best, mid-range cards currently on the market.
Just to give you an idea of how the various GPUs compare, starting with the R7-260X: 260X=750+/-, 265>750ti, 270 has no direct competition from Nvidia's current line up, 270X<760, 280>760, 280X>770, 290>780.
It's important to build a balanced system, where you're not compromising and buying a cheap CPU, motherboard etc. just so you can afford the best GPU, because then you won't be getting the best performance from that GPU and future upgrades could be very limited.
The G3258 is a very strong budget gaming CPU (at stock clocks, competes with the Athlon 760K (A10's, CPU-wise)) and can be overclocked to match the performance of an i3 and FX-6300 even. However it can only be overclocked, to that extent, on a Z97 motherboard.
So either way, you have some choices to make, but just understand how to properly compare CPUs and be weary of other components effecting system performance (HDDs) before you pass judgement on a "little dual-core". ;)