The problem you're encountering is that random.randint(1,UPPER_BOUND) is being evaluated once at the time the inner() function returned by runner() is called. What you need is to delay the evaluation until later.
You could try something like this:
>>> def runner(f, callable):
...   def inner():
...     for i in xrange(1000):
...       f(*callable())
...   return inner
... 
>>> runner(f, lambda: (random.randint(1, 1000),))()
603
385
321
etc.
Note that callable is called each time the original function f is called. Also note that callable must return a sequence type, like a tuple or list.
Edit: if you need to pass other arguments to f you can do it with something like this:
>>> def runner(f, callable):
...   def inner(*args, **kwds):
...     for i in xrange(1000):
...       pos = list(callable())
...       pos.extend(args)
...       f(*pos, **kwds)
...   return inner
... 
>>> def f(a, b, c, d = 3):
...   print a, b, c, d
... 
>>> runner(f, lambda: (random.randint(1,1000),))(3, 5, d = 7)
771 3 5 7
907 3 5 7
265 3 5 7