It's quite tricky.
You need an oscillator, counter and some gates to switch on/off LEDs depending on the count and resetting it when it reaches the maximum value.
The first step is to build a truth table, by convention inputs to the logic gate, from the counter are A, B, C, D etc. and the outputs from the gates driving the LEDs are some other letters.
For example in your case:
There are four states, so you need a two bit counter 2
2 = 4, if you needed five states, you'd need three bits 2
3 = 8 and reset the counter when it reaches five in binary. Fortunately you don't need any reset circuitry.
A B | X Y
0 0 | 1 0
0 1 | 1 1
1 0 | 0 1
1 1 | 1 1
X = (A.B')'
Draw the circuit (see attached).
Do the same for Y.
Plenty of tutorials on Boolean algebra can be found using Google, here's a good one.
http://www.doc.ic.ac.uk/~dfg/hardware/HardwareLecture01.pdfI think the 74HC series is best for what you want because it can drive LEDs directly, is low power and will work from two AA cells connected in series. TTL is rubbish, it's fussy about the power supply (4.5V to 5.5V) and uses lots of power, CD4000 is slightly better but you'll find that if you've connected an LED to an output it'll be dim and you can't use the same output pin to drive other gates because the LED will reduce the voltage to much.
Rather than messing around with a 555 timer and counter, I'd recommend the 74HC4060 which has an oscillator built-in. All you need to do is use two outputs adjacent to each other for A and B, for example, Q5 and Q4.
http://www.fairchildsemi.com/ds/MM/MM74HC4060.pdfI hope you can now see why it's easier to use a microcontroller for tasks like this.