If you're wanting something that doesn't require programming, use a 555 timer from Radio Shack. You just have to hook up two resistors and a capacitor to set the oscillation frequency. Although it only has a single output, it will work for your case too. Tie one LED's anode to your voltage source, a resistor to the cathode, and connect that to the 555 output call that A. Then connect the anode of a second LED to the 555 output, then a series resisitor to the cathode, and then that resistor to ground.
Call that B. A square wave will be coming out of the 555. Everytime it is low, it will provide a ground at the output, so A turns on, and B turns off. Then when the pulse rises, A turns off, and B turns on. Repeat. So there you have two alternating LEDs. Look up 555 timer connection diagrams and frequency calculations on the mighty google. You can change my +5v to a +9v in the diagram and use a battery. A 555 can use 9v easily, so you don't even need a regulator. Just make sure the resistors in series with the LEDs are able to limit current through them to no higher than 30mA (sometimes 25) based on whatever voltage you decide to use.