is it possible to implement a system with plausible denyability that is at least as strong as accepted cryptographic primitives (AES-CBC, SHA1-HMAC, e.t.c.) yet is not a lossy filesystem?
Yes, in a way. TrueCrypt and it's successor VeraCrypt support hidden volumes. They work by embedding a hidden encrypted container inside an encrypted container. You can protect the "inner" or "hidden" volume from being partly overwritten if you have access to it. But see Mark's comment for a gotcha. There are more; the TrueCrypt manual explains some of them.
This goes for StegFS, too. StegFS is only lossy if you don't provide it with the passwords to all the security levels you're using.
So you can easily construct a steganographic filesystem which doesn't lose your files - but in order for the filesystem to not overwrite them, it needs to know where they are, and this can only be achieved if you tell it the necessary passwords/passphrases before starting to work on the file system.
Have your cake and eat it, too
This is from your question in the comments:
Basically my biggest question was whether you can derive the place to store the file given the password, and somehow there would be a function that would allow you to find a free spot, yet would not reveal used spots
Again, if you provide the system with all the relevant passwords, this is easy. A very simple way to come up with stable disk storage locations based on passwords is by using hash functions - hash a password, or any other combination of identifiers, and get a stable number, which you can use as a pointer to a disk storage block.
If you DON'T want to provide all the relevant passwords, then it becomes much, much harder, and file system efficiency will suffer greatly.
First, you'll have to agree on an important point: The file system storage space is limited. If you have, say, 1 TB of space, and you have 1 GB of hidden files stored in it, then no matter how good the system is, if you write 1 TB of files to the disk, your hidden files will get overwritten. This is impossible to avoid.
But there may be methods to make sure that the files only start to get overwritten after you copied the first 999 GB to the disk.
Consider the following block allocation scheme:Whenever your file system requests a free storage block, a counter gets incremented and the counter determines which block to allocate. This means that you won't ever allocate a block that's already used as long as there still are free blocks on the disk. So you don't need to worry about overwriting hidden files as long as there is still free space on the disk.
The idea comes with a number of problems. For example, in the presented form, this doesn't work so good because you can immediately see how many blocks were allocated. Then you could count the number of blocks currently assigned to visible files and if that differed greatly from what you came up with, you could infer that there are lots of blocks assigned to hidden files. The other explanation would be that these were blocks of files you had deleted, but that's another problem with this system: There's no easy way to claim blocks of deleted files - if you want to reclaim the space of deleted files, you'd have to run special defragmenter software that reorganized all the data on disk.
There's another idea that might work a little bit better: You can have the block allocator for visible files allocate free blocks by allocating blocks 1, 3, 5, 7, 9, ..., and eventually coming back in reverse to claim the even blocks ..., 10, 8, 6, 4, 2.
Then you could have the allocator of the first hidden level allocate blocks starting at 2, 6, 10, 14, ...
Then you could have the allocator for the second hidden level allocate blocks starting at 4, 12, 20, ...
and so on. Each level L would provide 1/2^L of the total available space before starting to mess with data stored in other levels. Depending on how much data you stored on the various levels, level 1 could get away with storing more than 50% of data before starting to overwrite data in all the other levels.
(BTW: This would have a side effect: In this system, if you wanted or needed to, you could prove that there were no more hidden levels beyond the last one by storing twice the number of blocks that were actually assigned to it in it. This would overwrite the data of all the lower hidden levels. E.g. If you wanted to prove that there were no more hidden levels beyond the first hidden level on a 1 TB disk, you'd just have to store 500 GB of data in it, and if you used the file system without any hidden levels, you could store the full 1 TB)
But does plausible deniability work in real life?
I'm very sceptical about whether plausible deniability works in real life (generally, not just with TrueCrypt/VeraCrypt/StegFS).
I imagine two cases in which you might be forced to give up your encryption keys / passphrases:
You're legally obligated to give them up because law enforcement in your country has the right to request them, and a judge can hold you in contempt if you don't give them up
You're facing some criminal who is willing to torture the keys out of you.
In both cases, I fail to see how saying "there really aren't any hidden files on my computer besides the ones I showed you" makes a practical difference from "I don't remember the password for the encrypted file you see right here, but I remember it is last year's tax return statement."
Both law enforcement and the criminal probably won't believe you either way (there is a reason why they're talking to you! they expect you to have some specific documents they haven't found yet, after all), and they'll use whatever methods they have at their disposal to make you give up the key/passphrase. You're better off with law enforcement, of course, because the methods they can use are much more limited in civilized states.
Just think about what it tells an attacker about you if you use StegFS: It means you're trying to hide files. So how many files do you have to reveal before you can plausibly explain there is nothing more to reveal? This might actually work against you: You can't plausibly show that you've revealed all your hidden files, so a court in a country where the law allows for it might hold you in contempt indefinitely because you can't prove your innocence...
If you do live in a country where a court has to prove your guilt instead, then what would most likely happen is that the police confiscated all your drives and sent them to be analysed by a forensic unit to see if they could find a way around your denials. They probably wouldn't be discussing your steganographic file system with you in order to find out how plausible it was that you kept hidden data on it. So in that case, again, it wouldn't matter whether you used a steganographic file system or simply encrypted your data.
Plausible deniability through steganography is a nice idea, but I seriously doubt it works in practice. https://xkcd.com/538/ is somewhat related to this - the real world doesn't always conform to what we're imagining it to work like.