If you ain't scared of the terminal and a little coding, you can use the format FireFox exports to. It's a single html file with everything stored in one big with folders stored as headers and a sublist. All the urls and metadata are stored in the tags.
It should be relatively easy to make shell script that takes some arguments—e.g. action (add or remove), type (folder or link), url, and title—and modifies the file appropriately, programmatically taking metadata like creation/modify time (firefox stores them in unix time) from the system and favico from the website. That way it will work with any firefox anywhere.
If you want something more full featured, buku looks promising, although I haven't tried it. For a gui keditbookmarks—which is a standalone, despite being part of KDE—looks like a simple interface that can import/export in firefox, opera, netscape, or Internet Explorer formats, as well as export to a "printable html file" (which I assume meets your definition of "readable") and should open links in the system's default browser.