Which Haftarah is read with the least frequency?
Going through all of the possibilities (already mentioned, and that I can think of) mathematically, using the data on frequency of year types provided on Remy Landau's page, and the tables of kevios in Jewish Chrononomy, by Yehudah (Leo) Levi:
Miketz: usually that's Shabbos Chanukah. The exceptions are the year types זחא (regular) and זחג (leap). These account for 10.13% of all years.
Second Shabbos of Chanukah (Chanoch's answer): this occurs in years of type זשג (regular) and זשה (leap). These account for 18.44% of years.
Mishpatim: is Shabbos Shekalim in all regular years except השא, Shabbos Rosh Chodesh in זחג (leap), and Machar Chodesh in זשה and בחה (also both leap). The remaining year types, when its regular haftarah is read, account for 23.83% of years.
Vayakhel: in regular years it's almost always combined with Pekudei (and in the remaining one, השא, it's Parshas Hachodesh). In leap years, it's usually Parshas Shekalim, except in years of type החא and השג (this year is the latter). These account for 10.53% of years.
[The Ashkenazic custom is that the haftarah for Vayakhel is the same as that for the second Shabbos of Chanukah, I Kings 7:40-50. Since both can never occur in the same year, this portion is read, according to that custom, in 10.53% + 18.44% = 28.97% of years. However, the Sephardic (and Chabad) custom is that the haftarah for Vayakhel is I Kings 7:13-26.]
Pekudei: in all regular years it's either Parshas Parah (הכז) or Hachodesh (all of the rest of them). In leap years of types החא and השג it's Parshas Shekalim. The rest of them, then (when its haftarah is read), account for 26.32% of years.
Tzav (msh210's answer): This assumes the custom of reading the special haftarah of Shabbos Hagadol, and there are many variant customs about that. [Some always read it, others never do, still others (including Chabad) read it only when it coincides with Erev Pesach, and I believe the Gra's minhag was exactly the other way around - to read it only when it doesn't coincide with Erev Pesach.] But assuming the first custom, then Tzav's own haftarah is never read in regular years; in leap years it can be Parshas Parah (זחג, זשה, בחה), or Zachor (השג), and in Jerusalem it can be Purim (החא). The remaining year types, when it would be read, are 9.99% of years (Jerusalem) or 13.86% (everywhere else).
Tazria (Shalom's first answer): in regular years it's always combined with Metzora. In leap years it's Parshas Hachodesh in all except זחג, זשה, בחה. So this haftarah is read in 16.33% of years.
Kedoshim (Shalom's second answer): This assumes that indeed we read Acharei's rather than Kedoshim's when they're combined. In regular years this is always true. In leap years, Kedoshim is Shabbos Rosh Chodesh in זשה and בחה. In Israel only, it's Machar Chodesh in בשז and גכז. So it would be read in 16.33% of years in Israel, and 26.32% of years outside it.
Pinchas: outside of Israel it's read only in leap years of type החא and השג, so the frequency is 10.53%. In Israel it is also read in leap years of type בשז and גכז, and so the frequency is 20.51%.
Any others that I've missed?
So far it looks like the rarest one would be Tzav's, assuming Jerusalem and the minhag to always read the special haftarah for Shabbos Hagadol. Otherwise, the rarest haftarah would be Miketz's.
I believe Tazria alone (the story of Na'aman) is quite rare; very often it's either combined with Metzora (and we read the subsequent story of the four lepers), or some special week (HaGadol, HaChodesh, or the like).
Kedoshim's alone ("go tell Jerusalem about all its abominable acts") is also quite rare; when there's combined Acharei-Kedoshim, many communities break the usual rule (to use the second parsha's haftorah) and instead read that of Acharei. Even when separate, often Kedoshim winds up on some other special haftorah, and in the rare event that it wouldn't, Rabbi Soloveichik is quoted as saying you read the Acharei haftorah two weeks in a row! (Which I suppose makes it a "closet Haftorah.") We don't like going around talking about Jerusalem's abominations ...
I suspect it may be Tzav's, since Tzav usually coincides with the week of one of the many special haftaros that we read around that time of year. (I've also heard that the most rarely read haftara is Tzav's, but I don't remember hearing it from a reliable source.)
If it is Tzav's, that's pretty ironic, since Tzav's is one of the few haftaros mentioned in the g'mara.
A computer analysis of the 247 years and the haftaros read in each year will quickly yield an accurate result, however.
Shalom's 2nd answer, Kedoshim, is the correct answer according to the minhag that most Ashkenaz minyanim follow, and appears to be the case with the Sefardic custom too except that it is a different haftarah that is rarely read for them.
The prevailing Ashkenzaic custom is to always recite the portion from Amos on at least one week. Yechezkel, Chapter 22, is listed as the haftarah for "kedoshim".
However when Acharei and Kedoshim are recited together, the haftarah for Acharei (Amos) is read. This counts for all 12-month years.
Now let's look at 13 month years: - If Pesach runs Shabbat to Shabbat (like it did this year) then the Shabbat after Pesach will be Acharei and the one after that will be Kedoshim, and dependent on whether you are in Israel or not, the first or second of these will be 29th Nisan and you will read Machar Chodesh. On the other one, regardless of the sedra, you read from Amos. (In my community we are outside Israel and read Amos with Kedoshim).
If Pesach is Thursday to Thursday then Kedoshim is read on Rosh Chodesh, with that haftarah.
If Rosh Hashanah was on a Thursday the previous year then (in most communities) Acharei ends up before Pesach and is Shabbat Hagadol. The haftara read for Kedoshim is from Amos.
That leaves only one type of year. When Rosh Hashanah was a Shabbat and the year is deficient so Pesach begins on a Tuesday. Then you read Acharei on 26th Nisan and Kedoshim on 3rd Iyar with the haftara from Yechezkel.
That ends up about 5.8% of the time using the Remy Landau's chart (see other answer). In the last 50 years it has been read 3 times, then last time was 5757 (1997) and the next time will be 5784 (2024).