One could of course do this by picking the direction first, and then calculating the necessary pitch/roll/yaw changes to point that way, but I wonder if there is a good way to it without selecting the direction first? In other words, can you do it just by using your random numbers to pick pitch, roll, and yaw changes, assuming you only have the common random number generator distributions available.
First thing that comes to mind would be to do a random pitch change in [-pi, pi) then a random yaw change in [-pi, pi), but I think that is still going to be non-uniform. It doesn't have the same problem as the lat/long approach (because both pitch and yaw move on great circles, so you don't have anything like the variable length latitude line problem), but it still favors some points.
Including a random roll step in there changes it from two favored points to a favored great circle (I think...visualizing this is hurting my brain), but I suspect that no finite sequence of pitch, roll, yaw random steps determined by independent random numbers with distributions that are not changing based on prior selections can erase biases that stem from the fact that this approach is starting with the ship pointing at a particular point and having a particular initial orientation.
gattr suggests in another comment to look for clues around global illumination methods on how to solve this problem; his reference has the equations for picking polar coordinates from two random numbers generated from a [0..1] uniform distribution in section IV. B.
Just for prudence sake; one way of seeing why the normalization of n independent gaussian draws works. Is that the multivariate normal distribution in n-dimensions with independent coordinates is rotationally symmetric. One can visualize this in 2 dimensions by making a graph of the probability density and seeing it is invariant under rotations of the plane. This generalizes to higher dimensions. This is exactly the property that any direction is equally likely.