What happens is I made too many assumptions about save files. I dug into the code and found out some things so obvious, I did not see how I missed them.
First, Slots 0x1c and 0x1d are already used by the game itself. True, I don't really know what they save (other than it's at 0x0201c000, and has 0x1f00 bytes), but the save file gets corrupted when you change them by force.
Second, after expanding my search in the Fire red diassembly, I found that all bytes after 0x0203f178 are used up by some other processes in the game (also don't know which).
Third, trying to get Fire Red or above to run in my flashcard was pretty difficult. Apparently, some cards could not handle 128K flash, so they had to rely on external fixes to games that used them. They do so by saving only 64kb of memory (which is the amount truly used in Fire Red). So, at least on Supercard, any and all save memory hacks would fail.
So, I decided to think of a way to use absolutely no extra blocks, while still gaining some saveable bytes. 4kb is more than enough for most hackers, and as such, finding just one block worth of space would be enough.
First, a brief explaning of how Fire Red save blocks are made:
The block is composed of data, and a small footer that contains meta-data. It contains the block number (for loading order), save number (keeps two saves at a time, one save older as a fallback in case of the newer save being corrupt), checksum and a magic number. The number is always the same, and looks like a pointer, but no interesting code is present there. This takes the last 0xc bytes of the block.
Now, this is where waste comes into play. The saves are always stored in (at most) 0xf80 bytes of size. And other than some strain on the physical Flash, there are no reasons for that to be so (that I could find). Leaving the last 0x10 bytes of the block (4bytes + footer), a save block can store +0x70 bytes of data in each, at least.
The game saves the three Dynamic scrambled blocks (indexed by 0x3005008, 0x300500c and 0x3005010) that contain player, map and box data. The first one has 0xf24 bytes, the second has 0x3d68 bytes and the third one has 0x83d0 bytes.
So, they divided the larger ones in blocks of 0xf80 and some leftover bytes at the end.
The list of save sizes is at 083FEC94. other Roms shoud have something similar.
Changing those bytes around, we have the first block stay the same, leaving 0xcc (204) bytes at the end. The second changes the contents to 0xff0 for all except last block with 0xd98 bytes. That is a 0x258 (600) byte leftover. The third block goes through the same process, leaving the last with 0x450 bytes, with 0xba0 (2976) bytes remaining.
That leaves a total of 0xec4 (3780) bytes to be saved. That is pretty near the 4096 bytes.
So, using their own save and load routines, I input a small code that loads and stores to their respective sections our required data.
Note that the load and store routines still see the same (always reads 0x1000 bytes and stores 0x1000 bytes, in any case), but now some of our data is stored with them (like stowaway data).
As I mentioned before, 0x0203f174+ is used by a different process, but I am sure that 0x0203b174 to 0x0203f173 are used by the help screen (In a DMA copy of the last part of the VRAM, address 0x0600c000). So, disable them as in the original hack, and they are still safe. It's the 0203f800 flag region that is not.