After crawling the configure script, I think I have found your missing packet:
libmagickwand-dev. On my machine, after installing this packet, ./configure finally says:
Does Emacs use imagemagick? yes
NB1: as with other features (eg libxml2-dev for eww), I do not get the purpose of --with-feature:
- If the libraries and development headers are on your system,
configure will enable the feature even if you do not explicitly ask --with-feature;
- If the libraries and development headers are not on your system,
configure will ignore --with-feature and exit with status 0.
NB2: This has been tested on Ubuntu 14.04; libmagickwand-dev seems to exist in Debian too.
NB3: A general "methodology" to figure out the necessary packages from the
configure script: