The Talmud (Pesachim 54b) states that only for Tisha bAv must we be stringent for Bein Hashemashot. There is an opinion in Rishonim that only regarding the Bein Hashemashot at the beginning of the day is Tisha bAv unique, but all fasts require being stringent at the end because we have to wait until it is certainly night to uproot the current status (chazaka) of the day. Most Rishonim though do not make such a distinction (Arukh haShulchan OC 562:9).
In any event, as you alluded R Yossi holds that Bein Hashemashot starts only just prior to nightfall, and in general we do not combine Safek Derabanan Lekula with a rejection of R Yossi's view to provide a double leniency (Shaar Hatziyun 562:1). So either way we are going to wait until pretty close to nightfall. (Note that "nightfall" here would mean when average size stars come out, not small stars like we are stringent for regarding biblical issues like Shabbat. Likely even after 3/4 mil one can be lenient on other fast days as R Yehuda's time is up. CYLOR.)
R Tukachinsky's piece on this in his Sefer Bein Hashemashot is highly recommended.