J,
You're right - it is problematic in deed.
Android, iOS and Windows Phone all support client certs for EAS by now. But how you get the certificate onto the device varies:
Android can use /certsrv.
iOS can use iPhone Configuration Utility to enroll.
Windows Phone 7.x can install a pfx file. (I have not tested whether WP 8 works with /certsrv yet, but it should support pfx as well.)
There's more details on this over at my blog:
mobilitydojo.net/.../certsrv-vs-mobile-devices
mobilitydojo.net/.../client-certificates-in-android-ice-cream-sandwich
Using MDM there are different approaches depending on how the vendor has chosen to implement it, but in general it will be easier for the end-user with MDM.
There's also a test utility on my blog if you like to test client certs auth and troubleshoot:
mobilitydojo.net/downloads