Shlomo Hamelech used a 'Shamir' worm to quarry and cut the stones for the first Beis Hamikdash. Did they still have this worm for the second Beis Hamikdash?
If not, how were the stones cut (as no metal implements were allowed to be used)?
According to the Mishna (Sotah 9:12), the Shamir wasn't extinct until the destruction of the second Beis Hamikdash. ט:יב משמתו נביאים הראשונים, בטלו אורים ותומים. משחרב בית המקדש, בטל השמיר ונופת צופים;
Incidentally, there is no mention of the Shamir in Rambam. Ever the rationalist, Rambam doesn't believe in demons (which were associated with the Shamir). He held that it was okay to quarry and cut the stones outside the Beis Hamikdash area, and then be brought in (See Beis Habechira 1:8).
Likely, Rambam is following the Mechilta (Shemos 20:22) who holds that the prohibition only applies to the stones for the Mizbeach, and not to any other stones which may be hewn.