Scanning a 4 x 4 keyboard in software is not difficult and you can add a serial EEPROM chip like an Atmel 24C128 (16k) or 24C256 (32k) to store your keystrokes. Your requirements are well within the capabilities of all but the most basic microcontrollers. If you can dump the stored keystrokes via the serial port to a PC, then all you need is a processor with 10 IO lines plus the serial connections and 2k of program space (estimate).
A BASIC Stamp would work and probably meets your size requirement. Kronos
http://www.kronosrobotics.com has similar chips that I know will work, but you would need to supply your own board or buy one of theirs.
SparkFun carries a number of boards that would also meet the requirements. They are inexpensive and very well made and provide greater expansion opportunities and flexibility. The tradeoff is that the learning curve is a bit steeper and you would need a PIC programmer or a chip with a bootloader built in so you can download your program. You would also need to choose a development environment (C, BASIC, Assembly, etc.) to write your program.