Had another think about this.
Forget about infinite numbers of vertices, unless the doodah is gigantinormous on screen it's going to just look like a sphere after you reach a certain number of verts, so pick a maximum number first (64 sounds like a good amount for starters).
Then I'd do it with morphs, i.e. create your 64 vertex sphere model and morph it down to a tetrahedron (also with 64 vertices, however they all occupy one of the same 4 points). Just pick 2 adjacent distinct vertices and collapse them to the same point (this is easy to animate as well), then use some algorithm to try and make the distinct points as far away as possible from each other on the surface of a sphere. It's easy to morph models with the same number of vertices, it's just a linear interpolation of the 2 meshes (meshes must have the same indices).
You may wish to play around with a 3d modelling program to produce your intermediate shapes and just bake in the morph targets, I feel that would be better than just collapsing random vertices.
My only niggling concern with this method is if it produces non-planar polygons as faces. You may be better off using a wireframe representation if that is the case.
Well that's my 3rd suggestion and the one I like best.
EDIT: actually you may be better with 48 or 96 vertices as a starting amount since you can make a sphere with that number of vertices by subdiving the faces of an icosahedron (since an icosahedron has 12 verts, and each subdivision doubles the number of vertices).
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley