How do services like ShapeShift generate new addresses I found that ShapeShift generates new address for each transaction. How do they do that? Is it possible to exchange the coins in the same manner as ShapeShift do, but without the creation of new address?
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