I don't think you can get an arbitrary angle rotation, can you? because the result vector has to be perpendicular to either u and n. However, by rotating n, the result has the degree of freedom within one plane that's perpendicular to u. But what does it mean by 'having u and N x u'?

For the second question, I am not sure what angle we are considering.

N x (N x u) seems to be -u.

(One additional point: the figure here is assuming that the inner product between vectors N and u is 0.)

If N x u results in rotating the vector u by a quarter rotation, then N x (N x u) should perform two quarter rotations! In other words, this would result in rotating the vector u by 180 degrees, i.e., -u = N x (N x u). (ziqihen beat me to the punch!) Of course, if one were to repeat this two more times, then u = N x (N x (N x (N x u))).

The second question is asking how would one rotate the vector u by an arbitrary angle \theta in the plane with normal N. This requires a little trigonometry! If N = [0 0 1] and u = [1 0 0], then we know that u(\theta) = [cos(\theta), sin(\theta), 0] traces out a circle along the x-y plane, i.e., this expression rotates the vector u(\theta) by angle \theta. Any thoughts as to how one can extend this to 3D for arbitrary N and u?

Can we change the basis of u(\theta) = [cos(\theta), sin(\theta), 0] to {u, Nxu, N}? Then would it trace out a circle along the plane normal to N?

That sounds reasonable. :-)

I believe 3D rotations can be represented as matrices (linear maps). https://en.wikipedia.org/wiki/3D_rotation_group

Not exactly sure what is the most efficient way to compute and use it in practice though.