Square generator 1KHz to 1MHz with 1KHz precision
Direct Digital Synthesis may be over the top for what you want but it can certainly deliver the goods: -



Click on the picture to take you to the data sheet. It produces a sinewave but this can easily give you a square wave (on board comparator). With a 28 bit control register on frequency a 16MHz clock can be divided down to 0.0596 Hz if I read the data correctly and this is also the resolution.

The big disadvantage to the 555 brigade (yes, I have used one recently) is that you need to control it with SPI so a small micro interface to a keypad might be a good idea. Hey you can even use the micro for telling you what frequency it's generating (via an LCD).

Maybe the arduino can do SPI?