Well, as mentioned before there's the Mailbox app, there's using a Gmail Work/Apps account, there's using a service like NuevaSync, there's forwarding email to another account that does push (like iCloud or Outlook).
Native app for me as well. I have been trying a lot of them (gmail, apple, mailbox, cloud magic) and I keep coming back to apple. Just works the best overall.
Gmail. I could never get over the duplicate message bug that sometimes showed up when I tried to delete/archive emails. To me it's usually best to use the app specifically designed for the service.