Sounds like he wants a blockchain?
A blockchain probably isn't really what OP wants. But funnily enough it does meet all those criteria.
> what I’m after is a database to be embedded on client-side applications itself, be it desktop, browser, mobile, etc. Thats how most Blockchain clients work - on the client side, with APIs (usually RPCs) to chat with other programs
> Being immutable means that only new information is added, no in-place update ever happens, and nothing is ever deleted.
Immutability is exactly what blockchains were designed for.
> Syncable
Since blockchains are decentralized by nature, this also comes out of the box.
Of course if you choose a blockchain you have to deal with a host of other issues... performance, no SQL (in most clients), harder to debug, etc. But still a fun thought experiment