Wonderful.
I am betting facebook has something to do with this. All of my friends have had their accounts hacked recently, I am guessing I got a little of the splatter.
I'm betting it has a whole lot more to do with Facebook than your phone.
The only two ways the email would appear in your outbox are:
1. Someone violated your Gmail account itself, not using your phone (the "sent mail" folder syncs with yoru phone like all the others).
2. Someone hacked your phone and used it to actually send the emails.
#1 is a whole lot more likely, especially if your Gmail and some other account had a common password.
If your email and Facebook passwords are the same, then you need to change that. Right now.
Having the same password for any two accounts means that if someone hacks one of them, they have ALL of them. Your Gmail account should be very secure and very different from ALL other passwords anywhere. It contains really important data.
It's kinda sorta OK to have the same (or very similar) passwords for things like Androidcentral and Facebook. If someone ends up "owning" one of those accounts, there's (hopefully) very little important data they could mine from it.
But Gmail should still be a separate password having nothing to do with this algorithm, because that's where all your precious personal data resides. Same with your banking accounts and anything that contains data that's truly meaningful to you, and if someone else accessed that account you'd end up with pretty dire consequences.
And, in your case, that could include your Facebook account if you put a lot of data up there you'd rather not have others see (I could go on a rant about Facebook's security, but I use it too).