Sachverhalt: A. A.a H._ (geboren 1958) und sein Bruder G._ (geboren 1960) waren seit 1993 und 1985 für die Firma N._ tätig. Anlässlich der Generalversammlung vom 24. Mai 2004 wurden sie mit sofortiger Wirkung als Verwaltungsräte der Aktiengesellschaft abberufen. Nachdem die Firma die von den Brüdern angesetzte Frist zur Sicherstellung noch nicht bezahlter Löhne unbenutzt hatte verstreichen lassen, lösten diese ihre Arbeitsverhältnisse mit Schreiben vom 30. Juli 2004 fristlos auf und leiteten Betreibung über die ausstehenden Gehaltsforderungen für die Monate April bis August 2004 im Gesamtbetrag von Fr. 32'255.- (H._) und Fr. 41'410.- (G._) ein. Gegen die Zahlungsbefehle vom 29. und 30. Juli 2004 erhob die ehemalige Arbeitgeberin Rechtsvorschlag. Am 12. August 2004 stellten H._ und G._ bei der Arbeitslosenkasse des Kantons St. Gallen je Antrag auf Insolvenzentschädigung für nicht bezahlte Gehälter im Betrag von Fr. 37'359.- (H._) und Fr. 41'456.- (G._). Die Kasse lehnte die Begehren mit der Begründung ab, über die N._ sei bis heute kein Konkurs eröffnet worden; ausserdem entfalle eine Anspruchsberechtigung auch zufolge der bisherigen massgeblichen Stellung der Brüder im Betrieb der Aktiengesellschaft (Verfügungen vom 23. September 2004). Daran hielt sie auf Einsprache hin fest (Einspracheentscheide vom 19. November 2004). Das Sozialversicherungsgericht des Kantons Zürich (Entscheid vom 9. August 2005) und letztinstanzlich auch das damals zuständige Eidgenössische Versicherungsgericht (EVG; Urteil C 243/05 vom 16. Januar 2006) lehnten die dagegen erhobenen Beschwerden ab, wobei das EVG offen liess, ob und, bejahendenfalls, bis zu welchem Zeitpunkt H._ und G._ im Betrieb der ehemaligen Arbeitgeberin eine arbeitgeberähnliche Stellung eingenommen haben. A.b Nachdem am 20. Februar 2007 über die N._ der Konkurs eröffnet worden war, stellten H._ und G._ am 26. Februar 2007 erneut Antrag auf Ausrichtung von Insolvenzentschädigung für entgangenen Verdienst während der Dauer vom 1. April bis 31. Juli 2004. Die Arbeitslosenkasse wies die Gesuche mit Verfügungen vom 30. April und 3. Mai 2007, bestätigt mit je einem Einspracheentscheid vom 11. Oktober 2007, ab, weil H._ und G._ bis am 22. Juni 2004 als Mitglied bzw. Vizepräsident des Verwaltungsrates im Handelsregister eingetragen gewesen seien und daher von Gesetzes wegen nicht anspruchsberechtigt seien; zudem habe die ehemalige Arbeitgeberin sie per 30. Juni 2004 freigestellt, was einen Insolvenzentschädigungsanspruch ebenfalls ausschliesse. B. Das Sozialversicherungsgericht des Kantons Zürich wies die dagegen von H._ und G._ erhobene Beschwerde mit der Begründung ab, die Schadenminderungspflicht sei verletzt worden, weshalb die Kasse den Anspruch auf Insolvenzentschädigung im Ergebnis zu Recht verneint habe (Entscheid vom 14. April 2009). C. H._ und G._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, es seien ihnen Insolvenzentschädigungen für entgangenen Verdienst in der Zeit vom 1. April bis 31. Juli 2004 nebst Zins zuzusprechen. Die Arbeitslosenkasse schliesst auf Abweisung der Beschwerde. Das Staatssekretariat für Wirtschaft verzichtet auf eine Vernehmlassung.