Any database that uses SQL would work. The learning curve for SQL isn't that steep either, though you might have to find a database server that's within your budget. A decent database server can handle 2^20 records quickly and efficiently. Then you'll just have to write a script to input and output from the database to HTML periodically for static HTML. Dynamic server side scripting would be even easier, if you control the web server itself.
If you want to hire me to do it I would -- I'm not working for the past few months. E-mail me off-list.
