How to clear Android browser's localStorage?
Try: Settings → Applications → Manage Applications → Select Browser ("All apps" tab) → Clear Data. This would delete all the data belonging to the app. Quite like a factory reset, but just for that app.

Be careful while using this. Make sure you select the correct application (Its called 'Browser' some phones and 'Internet' on some) in the All apps list.  

You can accidentally delete your contacts and other important stuff if you are not careful