Basically as you pointed out, you need a rotation matrix. You can the rotation axis by calculating the cross product of the vectors obtained by using the new and old points and the angle is the angle formed between the vectors.
The above method assumes you are rotating about the origin. If you are not you need to subtract the point of rotation from the points, do the rotation, and then add it back.
Specifically, we have a point o (old point), n (new point) and we calculate (o x n)^ = (oxn)/[||o||*||n||] which gives the rotation axis. We then use <o,n>/[||o||*||n||] which gives us cos(theta) where theta is the angle of rotation. Take a look at this wiki entry for rotation matrices:
Rotation matrix - Wikipedia, the free encyclopedia
Do you have the translation vector or do you need to figure it out from the data? If you get it from the data you are going to have to solve a few simultaneous equations.