An update: It looks like I will phase out support for Firefox 3.0 and 3.5 at the same time. Reason is that they are technically very close as far as Adblock Plus is concerned, currently dropping support for the one while still supporting the other makes no sense. It makes much sense to stop supporting both Firefox 3.0 and 3.5 however, code complexity will be significantly reduced (not to mention that I barely test things in 3.0 and 3.5 already).
When will this happen? According to http://www.mozilla.com/en-US/firefox/all-older.html
support for Firefox 3.5 ends this month. However, Firefox 3.5.12 is still scheduled for early September and I doubt that it will be the last release. My guess is that there will be a Firefox 3.5.13 release in October after which Mozilla will stop supporting it. I'll probably drop support shortly after that, likely already in Adblock Plus 1.3 (I expect it to be released around October/November as well).
Current numbers indicate that around 13% of Adblock Plus users are still using Firefox 3.5. This number will likely drop significantly again when Mozilla makes their final update call. Around 6% are still using Firefox 3.0 - these are most likely a lost cause unfortunately.
However, Songbird and SeaMonkey will be problematic so maybe I'll delay this move to the next major Adblock Plus release after all. Current stable Songbird version is 1.7.3 which still uses Gecko 1.9.0. Songbird 1.9 successfully moved to Gecko 1.9.2 and the work on it is pretty far progressed - but I'm not sure whether it will be released to public once it is done.
Current stable SeaMonkey version is 2.0 which uses Gecko 1.9.1. SeaMonkey 2.1 Beta 1 is due soon, based on Gecko 2.0 (like Firefox 4). I would expect the final SeaMonkey 2.1 release a few month after Firefox 4 release - meaning early next year.
Thunderbird is not a problem: Thunderbird 3.1 has been released some time ago, it uses Gecko 1.9.2 so it caught up with Firefox 3.6. Thunderbird 3.0 will no longer be supported. Fennec isn't a problem either - it has been using Gecko 1.9.2 from the very beginning.