I am hosting my org's website with someone who will not allow me to change the MX records. But I have verified my domain. But google apps provides me only with @mydomain.com emails which need changes in mx records to work. How do I create users with @gmail emails in google apps?
You don't. You can't create @gmail.com addresses that are managed in Google Apps. Your only option as it stands is to use the @my-domain.com.test-google-a.com aliases that Google Apps creates for each my-domain.com email address you create. Obviously, this is not a good long-term solution.
It's really not OK that your host won't let you mess with your DNS records. You control/own your own domain name, right? You can transfer your domain to a domain registrar which will allow you to manipulate your DNS records, while retaining your actual web hosting where it is now.