Oli gave a good answer, but wait, mine will be better! :-)
Oli commented on the limited current from the coin cell, and that's indeed something to keep an eye on. This CR2430 cell gives 5 mA as maximum continuous. Let's see if we can manage that.
It's a good thing that you only need one LED on at a time, otherwise I would even consider the coin cell. This looks like a nice LED: typically 15 mcd at 2 mA.
Oli went for a SIPO (Serial-In, Parallel-Out) shift register for the LEDs and a PISO (Parallel-In, Serial Out) for the buttons. That saves you a lot of I/O but costs extra components. Can't we use the I/O of a microcontroller directly? 22 LEDs and 8 buttons is 30 I/Os, no problem, but we can do it a bit cheaper if we multiplex the LEDs in a 4 x 5 matrix. Normally this would decrease the LEDs luminosity by 75 %, but since we only have to light one LED at a time we can select one row and one column statically. So we need 4 + 5 + 8 = 17 I/Os.
Usual suspects for a microcontroller are Atmel AVR and Microchop PIC. Usually I'd avoid PIC for LED driving because it can't source or sink 20 mA, but we have a low LED current so no problem. PIC is also cheaper than AVR. The PIC16F57 has 20 I/Os, so that's enough. The datasheet says 22.5 µA maximum for a 32.768 kHz clock at 2 V, so at 3 V that still will be below 50 µA.
That's it. A microcontroller, a cheap crystal, 22 LEDs, 8 buttons, and 12 resistors (4 for the LEDs and 8 for the buttons. The PIC16F57 doesn't seem to have internal pull-ups). No shift registers needed.
When you multiplex a large number of LEDs individually the common way is to use an N x M matrix. The time is divided in N steps, in each step you activate one of the N row lines, and the column lines that correspond of the LEDs you want to enable. Note that the row lines can each carry M times the LED current, which asks for some buffering. Each LED is on only 1/N of the time, so to keep the normal brightness you must increase the current N-fold. Most LEds don't like this. Charlieplexing is not practical in ths situation because of the large currents involved.
From your question I understand that you want to enable only 1 LED at a time? In that case there is nothing wrong with Charlieplexing. A uC with 31 I/O pins can drive 900 LEDs. Sounds like the consruction will be a nightmare...
Update 5 years later:
Normal multiplexing or Charlieplexing is nice when you have too much time at hand, but when I had to control 100's of LEDs now I would buy a long strip of WS2801 LEDs.
Best Answer
There are several methods which can be used to drive large numbers of LEDs from a few IO pins.
The simplest is standard row/column display multiplexing. With this technique, you can drive \$( n / 2 )^2\$ LEDs with \$n\$ IO pins. Mathematically, the duty cycle is:
$$\frac{1}{minimum(\text{unique row patterns, unique column patterns})}$$
This means that this technique has a duty cycle of 100% when all LEDs are lit (or all rows or all columns are identical) and a duty cycle of \$1 / n\$ when a diagonal line needs to be lit (or all the rows are different). You're only guaranteed 100% duty cycle when lighting every LED or one LED (or zero LEDs, but that doesn't really count for much).
Slightly more complex is Charlieplexing. With this technique, you can drive \$n^2 - n\$ LEDs with \$n\$ IO pins. Only \$n - 1\$ LEDs can be lit simultaneously with this technique. Mathematically, the duty cycle is:
$$\frac{1}{\text{minimum simultaneous sets}}$$
where a simultaneous set is a unique group of LEDs which has a common anode or common cathode. (This hasn't been proven, it's just what I arrived at after pondering the problem for a minute. If duty cycle is important to you, you'll want to look into this further.) This is a much more complex calculation both intellectually and computationally than the equivalent calculation for standard multiplexing. Effectively, you get a duty cycle of \$1 / n\$ when all LEDs are lit but some (only some) patterns of n-1 or fewer LEDs can have a duty cycle of 100%. You're only guaranteed 100% duty cycle when lighting 1 LED.
The last method I'll mention is to use a shift register or IO expander. With two pins (Either the raw data/clock interface, I2C, or unidirectional SPI), you can control an arbitrarily large number of LEDs. The duty cycle for any pattern is 100%, but the update rate is inversely proportional to the number of LEDs. This is the most costly method. For 15 LEDs, it will probably be cheaper to just upgrade to a micro with that many IO pins.