What have Islamic scholars usually concluded about Dhul Qarnayn's time and what are the different views and based on what evidences?
I read the following on IslamQA:
Dhu’l-Qarnayn who is mentioned in the Qur’aan lived at the time of Ibraaheem (peace be upon him), and it is said that he became Muslim at the hands of Ibraaheem (peace be upon him)... https://islamqa.info/amp/en/answers/22029
But I did not understand what evidence they were basing their opinion on.
Strangely in this old fatwa they didn't quote sources even if in an Arabic version they did (see here). Basically the source is imam ibn Kathir's al-Bidaya wa an-Nihaya البداية والنهاية the translated sentence you quote is based on a statement of al-Azraqi الأزرقي (the author of a book called Akhbar Makka أخبار مكة، وما جاء فيها من الآثار) and other -not named- authors as ibn Kathir mentioned, here the Arabic quote from his book:
وقد ذكر الأزرقي وغيره أن ذا القرنين أسلم على يدي إبراهيم الخليل، وطاف معه بالكعبة المكرمة هو وإسماعيل عليه السلام. (Al-Bidaya wa an-Nihaya)
Al-Azraqi and others mentioned that Dhul-Qarnayn became Muslim at the hands of Ibraaheem (peace be upon him). And he made Tawaf with him around the Ka'aba and with Isma'ail.
and he added:
وروى عن عبيد بن عمير، وابنه عبد الله وغيرهما، أن ذا القرنين حج ماشيا، وأن إبراهيم لما سمع بقدومه تلقاه، ودعا له ورضاه، وأن الله سخر لذي القرنين السحاب يحمله حيث أراد، والله اعلم.
And he narrated from 'Obayd ibn 'Omayr and his son 'Abdullah and others that Dhul-Qarnayn performed Hajj by feet. And Ibraheem when he heard his coming came to meet him, and made supplication for him and appeased him. and Allah gave him the clouds which he sent wherever he wanted. And Allah knows best.
I found this in al-Azraqi's book here page 120ff (Chapter on the hajj of Ibraheem) and in this short version (page 22).
Like any library, Islam Stack Exchange offers great information, but does not offer personalized advice or legal verdicts, and does not take the place of seeking such advice from your Mufti, Imam, or other trustworthy Counselor.