I found a solution, which is still not quite fast enough though. Just save the vid paths in init, and initialize the capture objects in the first call of iter:
class VideoDataset(Dataset):

    def __init__(self, vid_paths):
        self.vid_paths = vid_paths
        self.caps = None

    def grab_idcs(self, idx):
        ...

    def __iter__(self, idx):
        vid_idx, frame_idx = self.grab_idcs(idx)
        if self.caps is None:
            self.caps = [cv2.VideoCapture(vid_path) for vid_path in self.vid_paths]
        cap = self.caps[vid_idx]
        cap.set(cv2.CAP_PROP_POS_FRAMES, frame_idx)
        frame = cap.read()
        return frame