I have thought about using an FPGA, but I don't have any experience with it, so I don't know what to look for.
Pretty good idea. A FPGA will do that, but a FPGA will be overkill for your needs.
You can use cheap CPLDs though. They are like a small FPGA, fewer pins, easier power supply and easier PCB layout. You also don't need external storage for the bit-stream (may save you a flash chip).
For programming these kind of chips I suggest that you just dive in and give it a try. Cheap FPGA and CPLD boards are available everywhere, and you should be able to go from nothing to a blinking LED within a day or two (It took me an evening the first time I did it, and most of the time was spent installing the toolchain).
Once you have this running, going from a LED blinker to a frequency synthesizer is just a few lines of HDL code.
You can even start without having a FPGA/CPLD at all by using a simulator. GHDL worked pretty well for me and has fine tutorial. http://home.gna.org/ghdl/
If you want to read about CPLD parts check the Xilinx CoolRunner2 line of chips. Super cheap dev-boards are available as well and the chip should be up for your task. If you're curious and want to dabble with FPGA I suggest either a cheap Xilinx Spartan board (I started with the XuLa200) or take a look at the Lattice parts. They sell development kits for around $25 including everything you need to get started. Oh, and they have cheap low pin-count parts as well. Something you don't find often in the FPGA world.