You can use the "Clear Private Data" button in the Firefox preferences to remove all private data. See How do I change preferences? for details.

However, that will also delete your bookmarks and other settings. You can restore your bookmarks from another computer by using Firefox Sync. In a future version of Firefox, we would like to add a way to clear history and cache without removing other data: https://bugzilla.mozilla.org/show_bug.cgi?id=542388

I wrote a simple add-on that puts a "Clear history" button in the mobile Firefox preferences: https://addons.mozilla.org/mobile/addon/clear-mobile-history/

Update: Because of a bug in addons.mozilla.org, installing the addon from the above page might not work. Until that's fixed, you can install it from limpet.net/clear instead.

History, form data and cache are really very different kinds of private data than passwords and bookmarks (the latter two having been assigned a more permanent meaning by the user through a storage action, while the first three are collected while browsing without the user specifically storing the data).

Basically you could define Bookmarks as History items that have been marked as 'to be persisted' by the user. Which means the History items that have not been bookmarked are safe to be regarded as volatile.

At least, that's how I see it in everyday use.

I find it a very annoying omission that cache, history and form data can not be deleted without losing permanently relevant data like bookmarks and passwords.

I can't wait till you implement a solution for this (no add-on hacks, just add it to the regular features already).