Store coordinates in 2d grid
I am not entirely sure what you are unhappy about, so I am going to assume you find it too cumbersome, so here is a "one line" way to do it:

import random
gen_coords = (lambda rows=range(5), cols=range(5): lambda width=50, height=50, side_of_scr=500: [[
    (random.randint(width/2, side_of_scr - width/2), height/2 + row * 2 * height)
    for col in cols] for row in rows])()


That is still ugly, so let us make an elegant solution, with better performance:

import random
def gen_coords(width=50, height=50, side_of_scr=500, rows=5, cols=5):
    lower = width/2
    upper = side_of_scr - width/2
    height_step = 4 * height
    gen_x = lambda : random.randint(lower, upper)
    def gen_row(row):
        y = (row + 0.25) * height_step
        return [(gen_x,y) for col in range(cols))]
    return [gen_row(row) for row in range(rows)]