@StR +1
Yes, Gmail treats "delete immediately" as "remove the label that corresponds to the folder" and all messages are still retained in "All Mail", whether they have any labels (folders) left or not.
The "move to deleted" is handled as you would expect.
And no, you do not have to set the trash folder to "push".
Push mail is optional, it's to enable instant notifications for new messages / updates, most users will only want it for the Inbox if at all.
When push is off, the app will sync your actions to the server instantly, and will sync server changes to the phone every 15 minutes.