To address this, I think we should examine why head cheese is made from a head in the first place.
There are two main reasons, the character of the meat attached to the head: paucity, toughness, and (lack of) accessibility; and the large amount of gelatin that can be obtained.
The meat on a head is well-exercised, and, with the exception of cheeks and jowl, thin, full of connective tissue, and wrapped around an oddly-shaped skull. It's difficult and not exactly worth the effort to try to remove it raw; after a good deal of work, you would end up with small shreds of meat that would probably best be braised anyways. Much easier to braise the head in its entirety and pick off the meat once it's soft.
The potential for gelatin is abundant in a head, especially assuming that the skin is left on (which it is for pig's heads): the skull of course contains plenty of albumen, the ears and snout are made of cartilage, and there's tendons around the jaw and heading into the neck.
Considering this, to make a substitution for a head, we should look for other parts of the animal that have these characteristics. The most obvious choice is the lower legs: pig trotters are in fact often added to the pot when making head cheese. Shanks all the way down to the ankles, and clean hooves from other animals, if available, would be perfectly suitable. The chicken feet you mention have the characteristic of yielding a good amount of gelatin, so they are a candidate. Tails are also a fine source of gelatin, with skin and plenty of connective tissue. Skin on its own would also be useful. For the meat, any of the usual well-exercised cuts should be suitable; a jowl on its own, the shoulder, possibly a diaphragm (hanger) from a cow.
In fact, one could very well make a delicious head cheese-like terrine using commercially-prepared gelatin with a full homemade stock, and any flavorful cut of meat that was available.