The Haftara for Tzav (a portion from the Babylonian annual Torah cyle) is from Jeremiah 7 (mentioned in Bavli Megillah 23b). The Haftara for the Israeli triennial cycle section that begins near the beginning of Tzav (at Vayikra 6:12) was from Malakhi 3. As in other matters, some customs from Israel made there way to some European communities. (Recall Tzav in non-leap years, and in some ancient customs even in leap years, is always on Shabbat HaGadol.)
Or Zarua (393) quotes a responsum of a R' Menachem about which of the two Haftarot is to be preferred for Tzav:
כתוב בתשובות למה לא בטלו עולותיכם ולא הנהיגו [להפטיר] בוערבה שמא משום דסיום דוערבה יום דין הגדול והנורא לכך לא הנהיגו להפטיר וערבה ואני מנחם רוח אחרת עמי מחמת וערבה ולקיים מנהג אבותינו שהיא תורה ושמשו גדולי הדור ורואה אני את דבריהם ואומר אני כשחל י"ד בניסן להיות בשבת שאי אפשר להפטיר אשר לא צויתי ולא עלתה על לבי ביום שחיטת הפסח משום דכתיב במועדו וא"א להפטיר ביום שחיטת הפסח גזי נזרך והשליכי ושאי על שפים קינה בשבת שהוא ערב הפסח ולהפיל לבן של ישראל עולי רגלים ומצאתי סייג לדברי כשבא לידי ספר של ה"ר משה בר משלם זצ"ל ההובא מארץ בבל והיה בהנביאים סימני הפטרות לפרשיות התורה לכל השנה וראיתי סימן צו את אהרן גבי עולותיכם ועוד סימן צו את אהרן גבי וערבה לה' ולכך כיונתי האמת לומר שפעמים מפטירין לצו את אהרן בעולותיכם ופעמים בוערבה ותנאי בדבר זה אם שנה פשוטה היא וחל צו את אהרן בשבת הגדול שלפני הפסח יפטירו בוערבה וכל שכן כשחל ערב הפסח בשבת ואם שנה מעוברת היא וחל צו את אהרן באחד משבתות של אדר השני ושבת הגדול יהיה באחרי מות אז יפטירו בעולותיכם לצו את אהרן אם לא תהיה אחת מארבע פרשיות באותה שבת ולפי שאין רגילות נוהג כן בכל שנה ושנה מפני שנת העיבור לפיכך נשמט מפי הסדרנים ונהגו תמיד להפטיר בעולותיכם לפי שהוא תדיר ע"כ התשובה עוד כתוב בתשובו' בשנת העיבו' הי' שב' הגדול בזאת תהיה והפטירו רבותינו בארבע' אנשי' לפי שבאש' כי תזריע לא יכלו להפטיר בנעמן מפני שהית' פרשת החודש והפטירו לויקהל משה בן ז' שנים ולאלה פקודי ותשלם כל המלאכה עד מלא כבוד ולא ויעש חירם ע"כ לשון התשובה
In short (the text is a bit confusing at times, probably somewhat corrupted), he writes that when Tzav is Shabbat HaGadol and all the more so when it is Erev Pesach, we use the Israeli Haftara (Malachi 3) because Jeremiah 7 is too mournful for such a celebratory day. But in a leap year when Tzav is not Shabbat HaGadol (nor one of the special 4 weeks in Adar) we use Jeremiah 7. He even cites an occasion when Metzora' fell on Shabbat HaGadol in a leap year and they read the Haftara about the 4 Lepors (Kings 2:7:3).
This solves your question about its relevance to the weekly portion. It is indeed a traditional Haftara for the weekly portion of Tzav that we are choosing to use then.
Now we understand the customs of reading on every Shabbat HaGadol (of non-leap years) and reading on Shabbat HaGadol that falls on Erev Pesach (of non-leap years). (See Yosef Ofer's article on the subject.)
Levush (OC 430) explained the connection of Malachi 3 to the time just before Pesach by noting that verse 10 is reminiscent of the obligation, which falls on Erev Pesach, of giving or destroying any leftover gifts from the previous 3-year tithing cycle ("Biur Maaserot"). Accordingly, we get two new practices emphasizing that connection: reading Malachi 3 only when Erev Pesach is after Shabbat which allows the Haftara to serve as an announcement for a future obligation (instituted by the Vilna Gaon (Maaser Rav 176)), and reading only in years 4 and 7 of the Shemitta cycle when Biur Maaserot actually happens (advocated by the Adere"t).
Another connection given by Levush between Malachi 3 and Pesach is from verse 23 which speaks of the final redemption which clearly parallels the themes of redemption on Pesach. This is the only connection I know of which is calendar independent and could justify reading Malachi 3 in all years. It seems quite likely though that that is not a very old practice.
Finally I note that many Baladi Yemenite communities do not read Malachi 3 ever (which makes sense given the Yemenite connection to Babylonian customs).
