Metric of axially symmetric asymptotically flat black holes in an arbitrary metric theory of gravity can be represented in the general form which depends on infinite number of parameters. We constrain this general class of metrics by requiring the existence of additional symmetries, which lead to the separation of variables in the Hamilton-Jacobi and Klein-Gordon equations, and show that once the metric functions change sufficiently moderately in some region near the black hole, the black-hole shadow depends on a few deformation parameters only. We analyze the influence of these parameters on the black-hole shadow. We also show that the shadow of the rotating black hole in the Einstein-dilaton-Gauss-Bonnet theory is well approximated if the terms violating the separation of variables are neglected in the metric.