Yes, this is possible. All you need is for the web host to support sub domains and to find out their dns and email client settings too.
Then your DNS zone file will need the additional MX record for the staff domain added.
@ IN MX 10 aspmx.l.google.com.
staff IN MX 10 mx-record-provided-by-webhost.com.