Good news, this is now supported as of Winter '17:
Navigate to Setup Home | Apps | App Manager
You can either create a brand new app (1) or edit an existing one (2). If you edit an existing Classic custom app (3) you will need to upgrade it first with the drop down button on the right side of the screen.
When you're in Edit mode the way to change the Logo will be obvious to you...
Hope this is helpful. :)
I think this is not supported as of now. But you can vote these Idea.
Update: From Winter 17 this feature is supported. You can follow the steps of Fabrice's Answer or for more details check here: Change App logo in Lightning Experience
As of Summer '17, you can use a custom logo, but note the App Manager is expecting a 45x45 pixels square image. If you use a non-square, then the longer dimension will max at 45px, resulting in the shorter side being very short.