How to randomize holes in a mesh, like with a particle system?
What about using the Alpha channel on the texture? Create a random noise texture (or any pattern you want) and plug it in the Alpha channel. I think that the effect should be believable enough.

I would then add a simple bump map in addition to that, so the corners of the whole are a bit smoothed.

EDIT:

So obviously you need to play around a bit with the generated textures, but this is the way I'd approach it. Here is a sample:



This looks stupid because I didn't use a leaf texture or the proper model, but I think it would look quite good on yours, and it's completely procedural, so it will be randomly generated automatically and you can define and keyframe the size.

I've added a small gradient so the leaf gets browner closer to the wholes (you could blend this with a nice brown leaf texture), and a bump map, so the holes don't have a completely hard border.

This is the node setup:



Hope that helps.