How about a macro?
I have a worksheet to which I often want to add new lines, w/ selective copying of formulas, formatting, etc. for certain columns. To do that, I created a User Control (button) and attached a VBA macro that will prompt me w/ an Input Box for how many rows to add, then add them w/ the proper formatting, etc. If you are familiar w/ recording and modifying macros, it should be relatively easy to create something similar for your purpose that will first unprotect the sheet, then re-protect it after the rows have been added.