>But you can't always use gradient descent. Backprop requires access to the inner workings of the function

Backprop and gradient descent are not the same thing. When you don't have access to the inner workings of the function, you can still use stochastic approximation methods for getting gradient estimates, e.g. SPSA. In fact, there are close ties between genetic algorithms and stochastic gradient estimation.