A trick I've heard about (but haven't tried) is to create a dummy file with junk in it, fighure out where that file starts on flash, then make sure you skip that many bytes (and don't write past the length of the file) when writing to the flash device. I don't particularly like the sound of this, but it does have the potential of being the cheapest in terms of interface hardware and software development.
This will work only if you are lucky enough to get the file allocated all in a single fragment. In general, a file on any filesystem (FAT, NTFS, etc) can be fragmented into multiple chunks, each chunk being an integer number of clusters. The cluster size can be any power of 2 between 512 bytes and 64K.
It just so happens that my day job involves low-level systems programming with filesystems and partition tables for data backup. Writing code to create a new file in a FAT filesystem is definitely non-trivial, especially if the file name doesn't fit in the old 8.3 character format. There are interface chips out there (forget the name) that solve this problem for you.