Solution: Control-click on Safari 4 Beta's Dock icon, and select New Window from the contextual menu. A new window should open, and all of the actions you took (post-freeze) will execute rapidly in this window. You may then close that window and return to the original, which will be working again.
Once frozen, I do not think Command-N will work, so you really have to use the Dock. Also, once one tab has frozen, clicking into any other currently-open tab will cause it to freeze as well. It would be nice to have a script for this, but despite it being very simple, I am far too lazy to write one.

