I'll mention the obvious assumption of Newtonian mechanics, as rigid motion is impossible with special relativity. Also in a finite set of points each should have a finite positive mass. For the base case (not requiring that far away points don't interact) Spivak's condition "not all points are colinear (2D) or coplanar (3D)" is indeed sufficient. I'm ignoring time dependence, since you can just apply the theorem pointwise in t. Here's a sketch for a proof by construction. It could definitely be either more concise or formal, but hopefully it's helpful and mostly correct.
Definition:
A force between two point masses is central if it is parallel to the separation of the points.
Lemma 1:
Given a set of point masses (with positive mass) and external forces acting on those points, rigid motion is well defined. That is, for every point there is a unique finite force such that:
i) The distance between points is conserved.
ii) The net force and torque is the same as given by the original forces.
Proof sketch:
Compute the total external force and torque acting on the body. Assume the body is rigid. Compute the acceleration of each point, which should be finite. Compute the net force acting on each point. Show the net force and torque is indeed the same as the net external force and torque. $\square$
Lemma 2:
Take 3 noncolinear point masses and forces acting on those points perpendicular to the plane the points span. Then any torque is parallel to the plane, and exactly one of the following is true:
i) All the forces are zero.
ii) The net force and/or torque is nonzero.
Proof sketch:
Starting with the first claim, since torque is defined as a cross product involving the force, it is obviously parallel to the plane of the triangle.
If all the forces are zero, there is no net force or torque, so we are done. So assume there are nonzero forces. Then if there is a net force, we are done, so also assume no net force. It is therefore sufficient to show that at least one nonzero force and zero net force implies a nonzero net torque.
Choose the frame of reference such that the plane of the triangle is horizontal and the center of mass is at the origin. Since the net force is zero, at least one of the forces is pointing up and at least one is pointing down. Then either:
i) One of the forces is zero. The net torque has a component parallel to the vector from the origin to either of the points with nonzero force.
ii) Two of the forces point in the same direction. The net torque has a component parallel to the edge between the two forces that point in the same direction.
Since the torque is nonzero, there is work being done on the system. Changing the origin of the reference frame does not change the work done, so there is nonzero torque in all inertial frames of reference. $\square$
Lemma 3:
Pairs of equal and opposite central forces don't contribute to the net force or net torque.
Proof is basically just the definition of force and torque.
Theorem:
Given a set of point masses in $\mathbb{R}^3$ not all coplanar and each point with positive mass, and external forces acting on those points, there always exists a set of central forces acting between pairs of points such that the motion of the set is rigid.
Proof sketch:
By lemma 1, for each point there is a unique net force that is consistent with the external forces and rigid motion.
Choose any 4 points that are not coplanar, which exist by assumption. Call those 4 points T (as in tetrahedron) and the other points C (as in cloud). In our solution the points in C will only interact with points in T and not with each other.
For any point P in C, the vectors from P to the points in T are not coplanar and therefore span the space. Therefore there exists a set of forces parallel to the separations between P and the points in T such that the net force affecting P is that given by lemma 1, taking into account the possible external force on P. For all points in C, choose any such solution. Also add the equal and opposite reaction forces affecting the points in T.
Similarly, we can take a point Q in T. The vectors from Q to the other points in T again span the space, and so we can make the total force on Q match the force from lemma 1, taking into account the possible external force on Q and the reaction forces from the points in C.
We are left with 3 noncolinear points. Central forces internal to the triangle can't add components perpendicular to the plane of the triangle. We may therefore need to add some perpendicular correction forces to get to the net forces from lemma 1. However, all other points already have the correct force from lemma 1, and by lemma 3 we have not added any net force or torque when adding internal forces. Therefore the triangle already has the net force and torque required by lemma 1. Therefore the correcting forces can't add any net force or torque (in particular the component of torque parallel to the plane of the triangle) and by lemma 2 are all zero.
Since no additional component perpendicular to the triangle is required, we can again take any one of the points, and since the vectors to the two other points span the plane, we can add necessary internal forces to get to the net force from lemma 1.
We are then left with a pair of points. Any equal and opposite pair of perpendicular forces would add net force or torque and, like previously, the pair already has the correct net force and torque. We can then add a force to match either of the points to the force in lemma 1. And finally, by the same logic, the final point must have the correct net force, so it must match the unique net force from lemma 1. $\square$