The setup you are suggesting is possible and is suggested over pointing a root domain at Heroku.
To achieve this you would simply create these DNS entries, in this example these mail mx records are for Google apps but the solution applies to any such mail service.
- CNAME Record with the name 'www' and the value 'your-app-name.herokuapp.com'.
- MX record with the name 'example.com' and the value 'ASPMX.L.GOOGLE.COM'
- MX record with the name 'example.com' and the value 'ALT1.ASPMX.L.GOOGLE.COM'
- MX record with the name 'example.com' and the value 'ALT2.ASPMX.L.GOOGLE.COM'
- MX record with the name 'example.com' and the value 'ASPMX2.GOOGLEMAIL.COM'
- MX record with the name 'example.com' and the value 'ASPMX3.GOOGLEMAIL.COM'
Depending on your DNS host it might be that you have to use an '@' instead of 'example.com' when creating your MX records.
If you want 'mail.example.com' to point to your hosted mail service you might add a further CNAME record such as:
- CNAME Record with the name 'mail' and the value 'ghs.google.com'.
All the best.