I am working on a service for hosting an HD wallet for a user, generating new address for each transaction, but without hosting their private key.

The idea is to let the user export an EPK from their HD wallet (once this is supported) into a file of some sort. Then they continue to manage their private key in any wallet that they want.

My question is: what format should that file be? Perhaps a PEM file that looks something like:
-----BEGIN EPK-----
...
-----END EPK-----
-----BEGIN EPK SIGNATURE-----
...
-----END EPK SIGNATURE-----

The signature is necessary to prevent mitm after exporting and before uploading. Is there already an implementation of exporting EPKs that I can try out? I appreciate your thoughts

Brian Armstrong did this awesome interview with Kevin Rose a while back. He goes into some detail about how their system works.
http://techcrunch.com/video/coinbase-founder-brian-armstrong-on-bitcoin-security-foundation/518053205/

Just curious, what kind of exchange are you building (btc, ltc, ppc, etc)? I heard of a guy exchanging BTC for ISK (as in from the game, Eve Online).

You should still set it up and play with it to learn how it works. Definitely don't keep it actually running though because you're just going to raise your power bill and lose money.