After some test with various bootloaders (at various frequencies), I can say that signing using ATSHA204A with frequency below 8Mhz is not possible.
I've tried at 4Mhz and 1Mhz and in both cases the SecurityPersonalizer sketch doesn't work (ATSHA204A not found).
I think (it is just an hypothesis) it's because of the timings of the one wire interface which has a baudrate around 230kbs and maybe is too fast for a 4Mhz clock.
Do you confirm this bahaviour?
If so, I think it should be mentioned somewhere, for example:

• in the description page of the sensebender micro which should work below 8Mhz and it is equipped with ATSHA204A
• in the signing explanation page
• inside the SecurityPersonalizer sketch

Furthermore the SecurityPersonalizer sketch itself should check and display a warning if the frequency is below 8MHz and you are trying to use signing with ATSHA204A