The problem I'm struggling with is where to store the keys.
Yes, that's the hard part. One solution could be to not store the keys on disk
at all. Rather, supply them as arguments when you start your application. That way the keys are stored in memory only (and possibly also cached to disk (swap), but that's another story). An attacker would then have to gain access to your application's memory in order to access your data. I assume that to access content in memory would be considerably harder than to access content on disk.