Iteration and memcache for selected categorized random elements
Regarding image caching, this seems relevant.

Secondly, DRY this code up, it'll make your code more maintainable: 

fileinfos = FileInfo.all().filter("category =", "eyes")
fileinfo = fileinfos[random.randint(0, fileinfos.count()-1)] 
url = images.get_serving_url(str(fileinfo.blob.key()), size=420)


Should have it's own function (forgive my py):

def get_random_image_url(category)
    fileinfos = FileInfo.all().filter("category =", category)
    fileinfo = fileinfos[random.randint(0, fileinfos.count()-1)] 
    return images.get_serving_url(str(fileinfo.blob.key()), size=420)

eyes_url = get_random_image_url("eyes")
nose_url = get_random_image_url("nose")
mouth_url = get_random_image_url("mouth")