How do services like ShapeShift generate new addresses
This is called Hierarchical Deterministic key derivation. 

New public keys, and by extension Bitcoin addresses, can be generated from a set of parent public keys. This way, the front-end of Shape-shift never needs to communicate with a "hot wallet" and can generate a new set of addresses for every user transaction.

To spend from these addresses, Shapeshift simply derives the corresponding private key (server-side) from its parent private keys.

Child private and public keys can be derived in parallel (front/back-ends), maintaining a fire-wall between them.

Intro to HD Wallets

For details on HD key derivation works, check a recent talk of mine at Scaling Bitcoin: https://youtu.be/OVvue2dXkJo
Slides here: https://teachbitcoin.github.io/wallets.html#/5