It really depends on on exactly what you try to accomplish with that database and what you need to store in it.
Then, you may have a trade-off between features or options the database could perform and the performance required from what you use.
For example, instead of having variable number of columns you may want to allow a fixed number of columns, or store numbers only on 1 byte or 4 bytes, or only allow one TEXT colum per row.. so that each row uses a fixed number of bytes allowing your code to seek through the database fast and use little code and memory for that ... etc .. what you wrote is too general to give you good suggestions.
As for your questions... yes, you would probably need a MICROCONTROLLER (a microcontroller is a micro processor with integrated storage for programs and ram and peripherals so a micro processor would be much harder to work with)
There are microcontrollers with EEPROM memory built in (but usually it's limited to 1K or thereabouts). There are easy to use EEPROM memory chips which can have up to a few MB of "disk space".
If the data is going to change very often, eeprom is not a good storage medium, it can only survive thousands to tens of thousands of writes. Alternative would be to use a flash based eeprom (a chip that fakes itself as an eeprom but uses flash instead) or fram (feram) which is much better but is also a bit expensive.
I guess you could use a sd card - there are sd card controllers that can be connected to the microcontroller and simplify reading and writing to a sd card).
With the minimal information you provide, I'd take advantage of the UART port most microcontrollers have and expose a serial port to the outside of the product. Or, I would use a serial-to-usb chip so that you could plug the device directly into usb.
Then, you can code a program into the microcontroller that could write records into the database or read them back to you using some simple commands, like
WRITECELL 1,2,100 (store 100 into row 1, column 2)
WRITEROW 1,5,6,7,8,smith (write a whole row #1 with the values separated by ",")
READROW 1 (send to the computer the whole ROW
READDB (send the whole database)
