There is also background, expression, and pose. You don't need to determine if it is the same person only if it is the same picture. I imagined something like mii avatars only much more realistic. Start with a standard mesh and change things like forehead width/height, width at eyes, cheeks, chin, then features like eyes (size, shape, color, placement) and all the things you mentioned. Then because it is a mesh, pose it and render with a patterned background to add a few more bits.
Discussion
One could map the bits to the parameters of a FOSS parametric human 3D model, but to render in a lightweight way would be the real trick, I think.
An SVG cartoon might be a lot easier, especially because rendering would be handled by the client device.