I do not have a list of working flash types but did a search for them. See below a list of what I found and think could fit. I also added where the specifications differ from the AT25DF512C. As I do not know exactly what is important from the specs I would appreciate it if someone with more knowledge on the topic could help to differentiate about what's important and what's not.
At least if one of the chips is not usable we can add them here, too - in a negative list. So we have information on those working and those who are not working in one place.

That's what I found:

SST25VF512A -> Datasheet: http://www.mouser.com/ds/2/268/25090A-708983.pdf

• operating voltage only 2.7 - 3.6V
• no Dual Output Read?
• 33 MHz max. frequency
• Couldn't find anything about JEDEC Standard Manufacturer and Device ID Read Methodology

SST25WF512A -> Datasheet: http://www.mouser.com/ds/2/268/20005016C-709021.pdf

• operating voltage only 1.65 - 2.9V
• no Dual Output Read?
• 40 MHz max. frequency
• Couldn't find anything about JEDEC Standard Manufacturer and Device ID Read Methodology

ISSI IS25CD512 -> Datasheet: http://www.mouser.com/ds/2/198/25CD512-010-LD020-258252.pdf

• operating voltage only 2.7 - 3.6V
• 100 MHz max. frequency
• supports JEDEC Standard Manufacturer and Device ID Read Methodology

W25X05-SN -> Datasheet: http://www.winbond.co.jp/resource-files/w25x05cl_e01.pdf

• operating voltage only 2.3 - 3.6V
• 104 MHz max. frequency
• supports JEDEC Standard Manufacturer and Device ID Read Methodology

Disadvantage of all of the above is that they seem to need far more than 2.0V to operate (bad for a battery sensor).

I think the AT25DF512C is best for the job but unfortunately I couldn't find a distributor in Europe. Digikey and Mouser (only places I know where to get it) do bill you $20 for shipping to Europe which I would like to avoid.