I think using a PIC would result in the least amount of components but depending on how familiar you are with PICs and programming for them, it may not be the easiest for you. This would be a good project to learn PICs with in my opinion. You could debounce the pushbuttons with software, increment or decrement a variable based on button pushes, reset the variable to zero based on another button push, etc. You would need to have some kind of sub routine that converted the value of the variable into 7 seg output. If you decide to pursue the PIC option, there are people here who could help you.
However, there are ICs that already exist that are specifically designed to do what you need. This IC:
CD4510BE Texas Instruments Counter Shift Registers
will count up, down, or reset based on button presses. It also has the built in functionality for you to cascade it for use with multiple digits.
You could use the first IC in conjunction with this one:
CD4543BE Texas Instruments Encoders, Decoders, Multiplexers & Demultiplexers
This second IC will decode the BCD output of the first IC into a 7 segment signal that you could use to drive the display.
You could connect the outputs of the second IC to transistors to drive the individual segments. It probably wouldn't be a good idea to drive the segments of the 7 segment digit directly from the IC but I haven't thoroughly gone through the data sheet to make sure.
You would need 4 of the first IC and 4 of the second IC but at roughly $.50 each, I think that would still fall into the cheap category.