We consider a generalised gravitational theory that contains the Ricci scalar curvature and a scalar field coupled to the higher-derivative, quadratic Gauss-Bonnet gravitational term through an arbitrary coupling function $f(\phi)$. We review both of the existing no-hair theorems, the old and the novel, and show that these are easily evaded; this opens the way for black holes to emerge in the context of this theory. Indeed, we demonstrate that, under mild only assumptions for $f(\phi)$, we may construct asymptotic solutions that describe either a regular black-hole horizon or an asymptotically-flat solution. We then demonstrate, through numerical integration, that these asymptotic solutions may be smoothly connected and that novel, regular black-hole solutions with non-trivial scalar hair emerge for any form of the coupling function $f(\phi)$. We present and discuss the physical characteristics of a large number of such solutions for a plethora of coupling functions $f(\phi)$. Finally, we consider the pure scalar-Gauss-Bonnet theory, under the assumption that the Ricci scalar may be ignored, and we investigate whether novel black-hole solutions may arise in this case.