The most obvious solution is to use some embedded DB which doesn't require any server software. This is where most people (I think) would choose MS Access. My intention is to be as portable as possible, and I don't like Access a bit, so I though about migrating to SQLite. I wasn't aware to the fact SQLite is quite a complete DB solution for such cases as my project. So I made the choice.
The next step was to migrate the schemas and data from the already running MySQL DB. My first Google search raised only complicated solutions, or costly solutions. Just before giving up, I started looking for some Windows GUI for SQLite, to allow me to insert the data manually. This is when I came across the freeware (not opensource) SQLite2008 Pro. Without the intention, I found myself with a nice tool which allowed my importing my existing MySQL schema information, and data, into SQLite. Even more surprising, the tool converted more complicated data types, such as auto_increment columns (autoincrement in SQLite).
Finally, some code modification was required. Luckily, I'm quite experienced with designing software that relies on databases, so I had a separate Python module which encapsulates DB specific logic. Importing the pysqlite2 library and adding two lines of code was all that needed to convert the entire application (over 2000 Python lines of code, mostly relying on DB) from MySQL to SQLite. Now the deployment of the project was stripped down to: install Python, install Python sqlite library. Cool.