In addition to what @crashdamage suggested (originally from @mikeone),
you can also configure:
Account settings (long touch on the account in the account list) -> Account options -> Deleting messages -> "Hide in the app, keep on the server".
This way, when one deletes the message, it is just hidden on that phone, and not actually deleted anywhere.
The caveat of this scheme is that eventually (periodically?), someone would have to actually delete all messages, - since nobody deletes them otherwise. (But that depends on the amount of mail and the mailbox limits imposed by the mail service provider.)
And as Mikeone described, - if you were to use POP3 and configure "do not delete messages on the server", then your individual mailboxes on the phones will be independent. But you might run into other problems and limitations pertaining to POP3 protocol (as opposed to IMAP). And you'd still have to clean the messages on the server periodically. Note, that one of the frequent POP3 limitations is the inability to serve concurrent connections to the same account.