You can have your exchange email forwarded to your gmail account. Just log into Outlook Web Access and setup a rule to forward all your mail to your gmail account.
To solve the problem of sending mail, I suggest making a second gmail account for sending only. I'm not sure about android phone, but you will either have to a) setup the account's reply-to address with the exchange's address, or b) setup the replay-to address on the phone.
And with Gmail, it is easy to link the accounts and send mail as a different account, using that account's reply-to address.
If you still have access to the original service, the best method by far is to use the tool ìmapsync (or OfflineIMAP as an alternative).
This will allow you to temporarily sync from the old service to the new one. It will retain all of the flags as well so that unread markers are retained. It will also retain any folder structures.
The second most common way of achieving this would require some careful coordination of mail routing. That would be a file copy of the source data which would normally be either in maildir or mbox format. This may also require help from the previous mail provider unless you have shell access to the old service.
imapsync is certainly the preferred method. Trying to do a transfer using eml files is not recommended. For starters, you will have lost all of the flags and folders. In addition, trying to do this for 5-6GB per user is going to take a LONG time. You will have to do it in stages.
Additionally, I'm not really sure that Pine or MUTT is going to help doing it the way you've outlined although you may be able to write macro's to transfer the files a few at a time.
UPDATE:
As we now know that sync from the original is not possible. The best way to script input from EML files to a maildir based system (if that is what you have, it is the most common storage format for Linux IMAP servers) is to use
getmail_maildir ~/Maildir/ < email_file.eml
getmail_maildir is part of the getmail package. This only works if you have direct access to the mail folders though this is commonly true with the better hosts. Not so sure about doing this with the other mail storage format mbox but I think that getmail also has a getmail_mbox command. In addition, the Windows application "IMAPSize" has a command for converting from EML to mbox.
So again, it is much easier to migrate the emails to a physical mail store rather than trying to pass everything through IMAP. However, it may be that you have to do this because the new provider cannot provide suitable access (as would be the case if migrating to GMail for example).
If this is the case, what may be best is to migrate the EML files to maildir format using a "synthetic" local maildir (there is nothing really special about maildir except the naming conventions so you don't actually need an IMAP server to use them) and getmail_maildir. Then use IMAPSync or OfflineIMAP to push from that local maildir to the new service. That way you don't need to mess with trying to script MUTT.
Best Answer
I know you asked for a simple solution NOT requiring a full-blown IMAP server, so I'm ready to get plenty of negative votes for my answer. :-)
Cyrus IMAPd is one of the most feature-complete open source IMAP servers around. With its ACL features you could first create a normal account for the duration of the backup, and when ready, just drop the write/delete access from your user account, so the mailbox will effectively be an archive folder with no way to accidentally delete your archived messages - at least not via IMAP.
Old and not so good, but a simple POP/IMAP server, uw-imapd can be more like install-and-forget solution, too. Just transfer your mail over IMAP to it and then your mail is accessible via IMAP or just by browsing /var/spool/mail/youraccount file. By making the file read-only with
chmod 400 /var/spool/mail/youraccountthe mailbox would effectively be a read-only mailbox.Dovecot is also a quite simple to setup and more secure & feature-complete than the uw-imapd I actually hate.
Anyway, I would install some IMAP server even if the initial setup can be more tricky. With your own IMAP server it's simple to add new accounts and archive more mailboxes, and you can reach the mail via several different methods; the mail client of your choice, via webmail if you install something like Horde, SquirrelMail or Roundcube, or even via the raw mail files.