Finding a minimum of a noisy function
Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement. 

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.


Differential evolution
Particle Swarm
Evolutionary algorithms


There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize. 

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia  (Computational optimization techniques section).