iPhone - Email and Messaging - Is there a way to delete multiple or all messages at a time?

Unfortunately, at this point, there isn't.

For the time being, you're left with one of two options, each which delete only one message at a time:

1) tap the EDIT button then use the minus+confirm DELETE

2) swipe your finger across the subject/teaser of the message you want to erase and confirm DELETE

Hopefully a multiple delete or delete all feature is coming in a firmware update to the iPhone.

UPDATE: Mail and Messages now both have a multiple delete feature (firmware 3.0 and later). While looking at your Mail inbox or SMS messages from a contact, you'll notice an "Edit" button in the upper right hand corner of the screen. To select multiple messages touch Edit then choose the messages using the circle toggles on the left side of the screen.

At the bottom of the screen, in Messages you can choose "Delete" or "Forward" while in Mail you have the choice to "Delete" or "Move" the selected messages.

UPDATE: The process for deleting multiple texts in Messages has changed in iOS 7. Click here for the updated instructions on how to delete multiple messages.