This is certainly possible with just about any small micro. You can either get one with enough pins or do some multiplexing for the buttons and have the LEDs driven by shift registers.
For 4 LEDs plus micro a coin cell is not really going to do, they have a very high internal impedance, generally only being able to supply a few mA before the voltage drops below a "usable" level. A few AAAs/AAs/Li-Ion would be more capable.
If you run the LEDs at a very low current and the micro at e.g. 32kHz, then it could be made to work, but unless there is a pressing need to use coin cells I'd avoid them.
Something like the 20-pin PIC16F1828, some buttons, and a few shift registers would be a cheap and easy way to go about this. Obviously if you prefer another brand of micro then there are many equivalents.
EDIT - some detail:
Shift registers
A shift register basically turns serial data into parallel data or vice versa. The one you will need is a serial to parallel shift register like the 74HC595. You have 3 main control inputs, a clock input, a data input and a latch input. The 595 has 8 flip-flops in a chain (flip flops store 1s or 0s) like this (4 shown):
When the clock toggles, whatever value is on the Data In pin (1 or 0) is shifted into the IC, and the last value shifted out (either forgotten or sent to another 595 if chained together) So you "shift" the data in one bit at a time till you have set all 8 flip flops to your desired value.
Then to output that data, you set the latch pin and the data appears on the 8 output pins. So 3 pins can be used to control 8 pins (or 16, 24, 32, etc)
Here is a picture of 2 595s chained together and driven from an Arduino:
There are loads of tutorials that go into much more detail than above out there, google for "shift register tutorial" and you get stuff like:
PIC shift register tutorial
Arduino 74HC595 tutorial
Another 74HC595 tutorial
Buttons
You can use a multiplexer like I mention above (check out stuff like the 74HC4051, 4052 and 4053), but since we are talking about shift registers it's worth mentioning we can use a parallel in, serial out shift register to read the buttons. The same connections, just the other way around - we latch the button states into the flip flops, then clock the data bit by bit into your microcontroller pin (i.e. read on each clock and store so you end up with 8 binary values)
Here is an example:
Final thoughts
From the comments and having had some time to think, I am leaning towards just using a micro with enough pins to have 1 per LED and button. This will be a smaller footprint than the shift registers, and involve the simplest firmware. I'd go for this at least to start with whilst prototyping.
Steven gave a very good answer, and multiplexing using IO pins is a common way of doing things (see Charlieplexing for a very economical multiplexing method) and certainly worth learning about.
The coin cell drive is certainly possible as mentioned. For a rough idea, I have a project prototype here using one of the PIC16F1828s mentioned above driving a 7-seg display, 2 buttons (the 16F1828 has internal pull ups so no resistors necessary) and 2 leds, which runs from a coin cell and sleeps between operations - the cell lasts for up to a year with normal use. So it's certainly possible, just adds complexity which you may want to save till later.
So in summary there are plenty of ways to go about this - if you have a breadboard why not grab the components for the options you want to try (use the dip versions then switch to SMD for final version if possible) and experiment at leisure.
