Here's what I did to fix this:
First I quit Mail.
Then I went into Gmail on the web, and into settings, then labels. I uchecked the box under System Labels for All Mail to show in IMAP.
I opened Mail after that, and noticed that my inbox was empty, and the archive folder was gone.
I quit Mail.
Then I went back to the settings and checked the same box that I unchecked.
After opening Mail again, it synced up all the mail just like I would expect. I did not touch the Archive setting or flag at all.
I did this for two different Gmail accounts with the exact same success. The Archive folder is the same as the All Mail folder that you most certainly had before Mavericks. If you don't like it, the only option is to not look at it. It's part of how Gmail functions and you don't want to delete it.
As far as not deleting, that is a "feature" of Gmail. The idea is that they give you so much storage for email that you should not need to delete email, rather just archive it. However, after the fix I went through, deleting seems to work the way I want, as in it puts the message in the trash on the client and the server. As far as I can tell, if you follow the steps above, Mail should do exactly what you want. The process took just a few minutes, and another several syncing the email back. Maybe 15 minutes total.
Cheers