Just to check my understanding. Would the solution to the second question be that the n not be a normal and instead by at angle theta to u. I'm not sure though is the resulting vector would still be in the plane. I think so.
We probably do not want to use a cross product operation to try to get rotation by arbitrary theta. That seems to become a chicken and egg problem because the result from a cross product is always going to be orthogonal to both vectors, and so we have to find a vector orthogonal to the one we want to start.
One way to answer this question (not the only way!) would be to use the basis vectors we already have.
So, for example, cos(theta)u + sin(theta)(Nxu) where u and (Nxu) are orthogonal basis vectors in the plane.