Anyone wanna weigh in as to (my difficulty) why there was no חשש לפשיעותא in the case of Herod destroying and then rebuilding the Temple?

Both explanations of Chashash apply there (1. there is no other place to worship/do the avodah and 2.how could they trust someone like herod that he would actually rebuild it. This is the same Herod that just before his grandiose reconstruction plan, had all the Hakhamim massacred almost to a man!
--
בענין סתירת בית כנסת על מנת לבנותה מחדש

רמי בר אבא הוה קני ביה כנישתיה (היה בונה בית כנסת)
הוה ההיא כנישתא עתיקא (והיה שם בית כנסת ישן)
הוה בעי למיסתריה ולאתויי ליבניה וכשורי מינה ועיולי להתם (היה רוצה לסותרו ולהביא ממנו קורות ולבנים ולקובעם בבית הכנסת החדש)
יתיב וקא מבעיה ליה הא דרב חסדא (ישב והסתפק בהוראה הבא של רב חסדא)
דאמר רב חסדא לא לסתור ביה כנישתא עד דבני בי כנישתא אחריתי (אין לסתור בית כנסת עד שבונים אחר במקומו)
התם (רב חסדא הורה כן שם)
משום פשיעותא (יש מחלוקת מה כוונת הגמ' בזה עי' להלן)
כי האי גוונא מאי
אתא לקמיה דרב פפא ואסר ליה
לקמיה דרב הונא ואסר ליה – מגילה כו ע"ב
הגמ בבא בתרא ג ע"ב אמר רב חסדא וכו' בהערת ארטסקרול שם: אמנם אסור לסתור ביהכ ואפילו חלק ממנו משום שהוא נקרא מקדש מעט והנותץ אבן של ביהמק עובר על "לא תעשון כן לה' אלהיכם" אולם לסתור על מנת לבנות מותר שנתיצה זו בנין הוא (תשב"ץ א' ב' ומשאת בנימין לג ומרדכי על מגילה פרק ד תתכו ושוע אוח קנב וביאור הגרא שם)
...אבל כשאין להם מקום אחר להתפלל בו בינתיים לדברי הכל אסור לסתור את הישן עד שיבנו את החדש אפילו במקרה שאין חשש פשיעה
ממשיך הגמ בב: ולא אמרן (האיסור של הריסת ביכ"נ) אלא דלא חזי בה תיוהא (כאשר לא נראו סדקים במבנה) אבל חזי בה תיוהא (באופן שיש חשש לנפילתו) סתרי ובני (אפשר לסתור ולבנות מחדש במקומו)
שם: כי הא דרב אשי חזא בה תהיוא בכנישתא דמתא מחסיא סתריה ועייל לפורייה התם ולא אפקיה עד דמתקין ליה שפיכי
וממשיך:
ובבא בן בוטא היכי אסביה ליה עצה להורדוס למיסתריה לבית המקדש (איך השיא עצה להורדוס לסתור את בית המקדש כדי לבנותו מחדש?) והאמר רב חסדא כו! (בהערה שם "שאף בסתירת ביהמ"ק היה חשש שיארע להם אונס ויפשעו ולא יבנוהו. והרמ"ה שגם החשש של דוכתא לצלויי היתה שם שכן כשסתרו את הישן ועדיין לא נבנה חדש לא היה להם מקום להקרבת קרבנות [שזה מקביל להעדר מקום לתפלה לגבי ביהכ] (אולם במשנה בעדויות ח ז למדנו שלדעת רבי יהושע מקריבים אף על פי שאין בית ראה תורת חיים ורש"ש)
מכאן נראה שאף כשרוצים לבנות את החדש באותו מקום של הישן אין לסתור את הישן אלא לאחר בניית החדש וכן אף כשרוצים לבנות את החדש ברוב פאר ויופי ולכן אע"פ שבנין הורדוס נבנה באותו מקום של קודמו וברוב פאר ויופי מקשה הגמ' שלכאורה היה אסור לסתור את קודמו לפני שהחדש נבנה (שער הציון שם ג-ד)
וממשיך הגמ': אי בעית אימא תיוהא חזי ביה (שבבא בן בטא ראה סדקים במקדש ואע"פ שעבודת המקדש בטלה בינתיים)
איבעית אימא מלכותא שאני דלא הדרה ביה (שאינה חוזרת בה מדבריה [כענין את הניתן אין להשיב...] דאמר שמואל אי אמר מלכותא עקרנא טורי (אם אמר המלכות אעקור הרים) עקר טורי ולא הדר ביה (תעקור הרים ולא תחזור מדבריה ולכן לגבי המלכות לא שייכת הוראותו של ר חסדא ובהערה מוסיף "רק לגבי סתם בני אדם יש חשש פשיעה והתרשלות בביצוע המוטל עליהם אבל לגבי מלכות אין חשש כזה שכן למלכות יש את כל האמצעים והיא גם מקפידה לקיים את דבריה [תשובה זו עונה רק על החשש לפשיעה שלגבי מלכות לא שייך אבל אינה עונה על ביטול עבודת הקורבנות בינתיים ץ הגמ' אינה חוששת לקושי זה לפי הטעם השני בהוראת ר חסדא (משום חסרון מקום אחר להתפלל) כי ההלכה היא כטעם הראשון (יד רמ"ה אולם לדעת רבינו יונה שכשאין להם מקום אחר להתפלל לכו"ע אסור להסתיר, בהכרח סתירת המקדש לא ביטלה את עבודת הקורבנות בינתיים כמו שכתבו תורת חיים והרש"ש
אבל עדיין קשה שלא חששו שמה מחשש לפשיעותא הרי הגמרא ממשיכה לספר על אודות אותו הורדוס שקם קטלינהו לכולהו רבנן ושבקיה לבבה בן בוטא ליטול עצה ממנו! (מפני שדרשו על הפסוק מקרב אחיך תשים מלך למעט עבדים כהורדוס וצאצאיו כמסופר למעלה על מה שאמרה אותה ינוקתא מבית חשמונאי)
אף על גב שרצה למחול על עונו ונמלך בבא בן בוטא שהוא זה שייעץ לו לשקם את המקדש! כבה של עולם ילך ויעסוק באורו של עולם (או בגירסא השנייה של הסיפור)
ושם מסופר שהורדוס ענה לבן בוטא מסתפינא ממלכותא (דהיינו הוא ירא מן מלכות רומי לה אני כפוף שיסתכלו בעין רע על הדבר) והלה יעץ לו עצה שיעשה בתחבולות הרי לקחו שם סיכון והרי גם היה חשש שמא חמת מלכות רומי יגמור לכך שבסוף לא יהיה בית כלל (כי לא ביקש רשות)
ובסוף הודו חכמים מי שלא ראה וכו'
באנצק תלמ ראיתי:
אסור לסתור ביה"כ אפילו כדי לבנות ביהכ"נ אחר (מגילה כו עב, רמבם תפילה פיא היב טושוע או"ח קנב )במקומו או במקום אחר (רמבם שם) ואפילו כשרוצה לבנות החדש מאותם העצים והאבנים של הישן (מגילה שם, ירוש' שם פג הא) ואפילו אם רוצה לבנות החדש מפואר יותר ויפה יותר מהראשון (מ"ב קנב על פי ב"ב ג ב בבנין הורדוס) אלא בונים את האחר תחלה ואח"כ סותרים את הישן
ברמבם הלכות תפלה פיא הלכה יג אבל אם חרבו יסודוסיו או שנטה בתליו ליפול סותרין אותו מיד ומתחילין לבנותו במהרה ביום ובלילה שמא תדחק השעה וישאר חרב
בטעם האיסור נחלקו בגמרא יש אומרים משום פשיעה (מגילה ובב) היינו שמא יארע להם אונס ולא יבנן האחר או שיתרשלו ולא ימהרו לבנותו (נמוקי יוסף ושיטה מקובצת ב"ב שם בשם רשב"א) ויש אומרים משום שעד שיבנו את החדש לא יהיה להם בינתיים מקום להתפלל (בב שם) ויש הבדל בדין בין הטעמים: כשיש להם מקום אחר להתפלל, שלטעם הראשון מכל מקום אסור לסתרו ולטעם השני מותר (גמ שם)

אם יש בינתיים ביהכ אחר להתפלל בו נחלקו על זה הטז שמתיר והמגן אברהם אוסר בכל מקרה וכן גם דעת האגודה ככ באליה רבה
היה להם ביהכ"נ קבוע אחר להתפלל בו, יש אומרים שמותר אף לטעם הראשון שלא אסרו אלא כשיש להם סתם מקום שאינו ביהכ"נ קבוע להתפלל (תוס ד"ה ואם לגי,: דוכתא לצלויי, נמוקי יוסף שם, מאירי מגילה שם, טז סימן קנב ס"ק א) לפי שאין החשש שלא יבנו לעולם אלא שמא בימים שבינתיים יתרשלו קצת והמקום העראי יתבטל ולא יהיה להם מקום להתפלל (נמוקי שם ועי מחצית השקל ס"ק א). ויש אומרים שלטעם הראשון אף ביש להם בי"כ קבוע אסור והלכה כטעם הראשון: משום פשיעה (רמבם כסמ וטושע שם) ויש מן הראשונים שפסקו כטעם השני (אור זרוע חלק ב סימן שפה)
אפילו כשכבר גבו כסף לצורך ביהכ"נ החדש ואפילו כשכבר קנו לבנים והן מסודרות ומזומנות לתתן לבנין אין סותרין את הישן שמא יזדמן להם פדיון שבויים וימכרו הלבנים לצורך המצוה (בב שם) ואפילו אם בנו את החדש ולא השלימו קירויו ינם רשאים להסיר קורות ולבנים מהישן ולתתן על החדש אלא יגמרו קודם את החדש (מאירי מגילה שם) גמרו את החדש אף על פי שעדיין לא התפללו בו סותרים (!) (עי תוס בב בב שם ד"ה אי הכי ושמ"ק שם)
אף אם באו להרחיב את ביהכ"נ ולסתור כותל אחד בלבד בונים מקודם הכותל החדש בצד הישו ואח"כ סותרים את הישן ויש מהראשונים שהתירו לסתור קודם אם אי אפשר בלאו הכי

אבל אם חרבו יסודותיו עיין ברמבם

צא וראה כמה חמור הדבר שלא נתנוה לרמי בר אבי לבנות בית כנסת חדש וזיל מרבנן לרבנן ולא התירו לא והדבר קצת תמוה ואומר אני הצעיר שפליאה דעת ממני שחששו בו משום פשיעותא כלל וכלל
ועוד הרי בית כנסת שחרב נשאר בקדושתו שעדיין לא עבר זמן מצותו וראוי לשפצו ולבנותו (רמבן מגילה כו ע"ב)
כפי שאיתא להלו במגילה כח עא ועוד אמר ר יהודה בית כנסת שחרב כו' ואין מספידין בו ואין מפשילים בו חבלים...ואין שוטחים על גבו פירות. כשם שנוהגים בהם כבוד ביישובם כך נוהגים בהם בחורבנם (רמבם תפלה פ"יא ה"יא) ומניחין לעלות בהם עשבים (ברייתא מגילה כח ב)...כדי שיראו אותם ותהיה להם עוגמת נפש! (משנה שם א גמ שם כט א ועי בפיהמ"ש להרמב"ם) או שיבקשו רחמים שיחזרו לקדמותם (רש"י שם) או תיכנע נפשם וישובו אל השם אם לא יכלו לבנותם (פיהמ"ש שם)