Kubernetes: detect and auto-update deployment on image update
Sounds like Weave's Flux answers your requirements:
https://github.com/weaveworks/flux
We have it installed in one of our customer's cluster and it works great. It will watch for changes to your Docker images and perform a redeploment. Kinda exactly how you described it in your question.
The project is a bit new so setting it up can be a bit tedious... But eventually it works!