Yup, I had to cut my own holes... but be not afraid! It's not that hard if you've got a good pocket knife. I cut all the holes after I got the covers on.
I got the paint at Pep Boys - it's Duplicolor flat black fabric/vinyl paint. It's holding up fairly well so far, but I'm going to have to hit the trim again b/c it's starting to chip in a couple of spots.
I don't think I'll have time to help you out before I leave town, but I'd be happy to lend a hand after I get back (if you can wait a couple weeks). The biggest tip I can give you is this: work slowly and pay attention to how the old covers come off - installation is the reverse of removal. Do one seat at a time, and take pictures if you need to.