Restart image sequence for each new particle?
Blender Particles has both an object and group feature.  You appear to already be using the object feature. With a bit of practice new particles can be added in 88 seconds or less.  We happen to show Materials and Texture for Blender Internal Render.  Cycles has a similar settings in the nodes.



Particle System panel showing location of group information.  Also showing some groups in the outliner window. Image above.



Material/Texture/Image Sequence/Offset and Start. Image Above.

Here is a video tutorial for creating a group.  It may or may not be the same version of Blender you are using.  You may choose a different tutorial on the topic of [groups]. I just did a quick search.

https://www.youtube.com/watch?v=R2Q6KcSho48

or the manual

https://docs.blender.org/manual/en/latest/editors/3dview/object/properties/relations/groups.html

One way to achieve your goal is to create a [group] of particles.


Each plane in the group can be different. Blender can use any of the planes in the group. This feature is in the particle settings use group. See image above.  I suggest you put at least 9 image planes in your group for variety.
This proposed answer does not use Python. If the OP has Python experience then the OP can do some of these tasks with Python.
The planes in the group will be different because you will take the steps to have different [start and offset and image selection quantity] values for them into the image sequence.
A suggestion is to create another plane as a duplicate of what you already have, then change the [start and offset].  The offset is within the image texture settings.  See image above.  Change to suit your needs.
If the original plane is in the group, then all duplicates will also be in the group.
Please verify and improve these suggestions and suit to your needs.