Are billboard particles with animated textures possible?
There are two parts to this question: making the particles face the camera, and then making the particles animated. I will address each separately.

Billboard Particles

This functionality is currently not supported in Cycles. That is not to say, however, that it is impossible. 

One simple approach is to parent a plane to the center of mass of the object, set a tracking constraint to the camera, set the particle system to dupli-object, and enable parent rotation to the particles:



With this method, not all of the particles are technically facing the camera perfectly. But I have found that the camera has to be pretty close to the object for it to be noticeable, so unless you are using a fish-eye lens or are trying to get macro shots, this should be acceptable for 99% of cases. The distortion also adds a bit of randomness to the size which can sometimes be desirable.

The other approach is to create another scene which renders using the internal engine, wherein billboard particles are supported, and then link the two objects. For this to work, you will have to configure a camera in Blender internal which functions the same as the one you have in cycles. This can take some time, because each engine deals with camera settings differently. Here's a Reddit post going into more details if you wish to do this.

You could also probably develop a script or a add-on which adds functionality. Unfortunately I don't know enough about Blender add-ons to detail this approach any further.

Animated Particles

tl;dr: there's a node in Blender called Particle Info which can be used in conjunction with a sprite-sheet to animate particles using some Math. 

I'm surprised that people have deemed this "impossible." It just takes a (complicated) node setup. I'm going to assume you know some basic discrete mathematics to set this up. You will need a custom mapping node, which you can either download or make yourself from this post. You will also need a Math.floor node which you can, again, either make yourself or download in this pack.

The first step is to convert your image sequence into a sprite-sheet. You can either manually do this in Photoshop or write a simple script to do this for you. This tutorial will detail how to do this with just 1 row, as seen in my example:



Note that it is perfectly possible to have more than one row, but it just takes some extra effort in the node editor. 

Next, create a plane set it as a dupli-object for the emitter. This will be the master particle. UV unwrap the plane and configure it to be exactly the size of the first particle as shown here:



The only thing left is the material. As it turns out, there's a node in Blender that gives all the information necessary to create animated particles like this called the Particle Info node. I was surprised I hadn't known about this already, since it seems so useful. The two values we want are Lifetime and Age. 

The approach will be different depending on how you made your sprite-sheet, so a basic knowledge of math functions will be useful. You can find many guides to dealing with spreadsheets in game design online, but I don't think its necessary.

The basic approach is to translate the uv mapping of the plane depending on how long the particle has been alive. So, for instance, right as the particle is spawned, it is on frame 1 (and has been translated 0 pixels to the right). Halfway through, it will be on whatever the middle frame is. So, if there are 16 frames in the animation, it will be on frame 8, and will have been pushed 7 tiles over. 

The node gives us lifetime and age. Dividing age by lifetimes gives a ratio from 0 to 1 that corresponds to how long the particle has been alive. Multiplying by the amount of frames in the particle animation gives a number that corresponds to the amount of tiles the uv needs to be shifted to the right, plus some extra decimal information that isn't necessary (since you never want to translate the uv, say, half of a tile). You can cut this off with a Math.floor node, giving all the information necessary to make it work.

Hopefully that all makes sense. Here's my node setup (applied to the plane) for the example sparkle animation with 16 frames shown earlier:




This divides the age of the particle by the lifetime, giving a percentage of how complete the animation should be (as detailed earlier)
This multiplication corresponds to how many frames there are in the particle's animation
You have to floor this so that, for instance, you don't shift over by half of a tile
This is the amount to slide over for each tile. For me it is always the reciprocal of the amount of frames, because a value of 1 will wrap around an entire time. I recommend using the Node Wrangler add-on to mess with this node directly to figure out the right value
Simply plugging everything into the custom mapping node in the x category, because there is one row


This will ultimately give you a vector which you can use on the sprite sheet as an image texture, which you can then use in your material as normal.

My final result (with some custom scaling and some other changes in the emitter) looks like this:



Note: I sometimes worry that I'm being patronizing to those that do know math, but I also understand that a lot of artists do not know much math, so I'd like to explain the node setup rather than just handing it out and not explaining it. Please tell me if my explanation is confusing and I will be happy to clear it up!