I think a PIC is a good option. I've used the internal EEPROM which is easy enough, and something like a PIC18F2550 has the I/O you need including USB, or serial which would be much easier to implement. If you need more memory then you can put an external EEPROM in.

There's a couple of BASIC compilers you might want to try that make programming them much easier. Still programming them in C is better.

What are the projects if you don't mind me asking?