Given two unit vectors $\hat{u}$ and $\hat{v}$, we can construct a vector perpendicular to both by their cross product:
$$\vec{n}=\hat{u}\times\hat{v}.$$
To obtain a perpendicular vector of unit length, just normalize $\vec{n}$:
$$\hat{n}=\frac{\vec{n}}{\|\vec{n}\|}=\frac{\hat{u}\times\hat{v}}{\|\hat{u}\times\hat{v}\|}.$$
Normalizing $\vec{n}$ requires the computation of $\|\hat{u}\times\hat{v}\|$. Since the norm of a vector is defined as the square root of the dot product of the vector with itself, it is impossible to normalize a vector without using square roots.
However, there is a way to look like you're avoiding square roots. If you can find the angle $\theta$ between the unit vectors $\hat{u}$ and $\hat{v}$ geometrically, you can employ the theorem that gives the norm of their cross product as:
$$\|\hat{u}\times\hat{v}\|=\sin{\theta}\\
\implies \hat{n}=\csc{\theta}\,(\hat{u}\times\hat{v}).$$
Of course, this method doesn't truly avoid square roots, since $\sin\theta$ is defined as a square root:
$$|\sin\theta| = \sqrt{1-\cos^2{\theta}}=\sqrt{1-(\hat{u}\cdot\hat{v})^2}.$$
Note: one need to be careful when working in spherical coordinates, as there are two conventions used for the notation of the polar and azimuthal angles. See https://en.wikipedia.org/wiki/Spherical_coordinate_system and the 2 pictures near the top. In this answer I am using the physicist's convention, since it complies better with your own notation.
To clear the first point of confusion: All vectors start at the origin. They can be added together visually by placing them head to tail, but you should always think of them as having the tail at the origin and the head pointing in whatever direction it's supposed to.
The cross product in rectangular coordinates and the cross product in spherical coordinates are the same thing. The only difference is the way we represent them in formulas.
Notation also seems to be confusing you. The basis in spherical coordinates works differently from the basis in rectangular coordinates. See http://mathworld.wolfram.com/SphericalCoordinates.html and scroll down to the listing of unit vectors for a complete account. Caution: This article uses the mathematician's notation. You will have to swap the roles of $\theta$ and $\phi$ in your head, or just write things down to keep track. e.g. $\hat{\phi}$ there is what we'll think of as $\vec{e}_\theta$.
Here is a working definition of the cross product:
The cross product of two vectors $\vec{a}$ and $\vec{b}$ is another vector, mutually perpendicular to $\vec{a}$ and $\vec{b}$, with the direction determined by the right-hand rule. The magnitude of $\vec{a}\times\vec{b}$ is given by the area of the parallelogram spanned by $\vec{a}$ and $\vec{b}$.
Note that this definition makes no reference to the choice of coordinate system; it works in rectangular and spherical coordinates.
Therefore, if $\vec{a} = (a,\theta,\phi)$ and $\vec{b} = (b,0,0)$ in spherical coordinates, to find the cross product we need to find the direction the vector is pointing and the magnitude from this information. The key to this is to find the angle between $\vec{a}$ and $\vec{b}$. Well, $\vec{b}$ points straight along the $z$-axis, so it suffices to find the angle of $\vec{a}$ relative to the $z$-axis, and if you draw a picture you should see that this angle is $\theta$. (It doesn't matter what $\phi$ is here.) The area of the parallelogram spanned by $\vec{a}$ and $\vec{b}$ is then $ab\sin\theta$. As for the direction, to be perpendicular to the $z$-axis the vector must lie in the $xy$-plane, so we need to find the direction in the $xy$-plane perpendicular to $(a,\theta,\phi)$. Then it suffices to find the direction perpendicular to $(1,\pi/2,\phi)$, which is of course $(1,\pi/2,\phi\pm\pi/2)$. The right-hand rule says we take the minus sign, so
$$
\vec{a}\times\vec{b} = ab\sin\theta(1,\pi/2,\phi-\pi/2).
$$
We can take the plus sign by pointing in the opposite direction, so
$$
\vec{a}\times\vec{b} = -ab\sin\theta(1,\pi/2,\phi+\pi/2).
$$
Finally, let's express the last vector in rectangular coordinates. It is
$$
(1,\pi/2,\phi+\pi/2)_{\text{sph}} = (\sin(\pi/2)\cos(\phi+\pi/2),\sin(\phi+\pi/2)\sin(\pi/2), \cos(\pi/2))_{\text{rec}} = (-\sin\phi,\cos\phi,0)_{\text{rec}} = \vec{e}_{\phi}
$$
according to the definition of unit vectors in spherical coordinates. (See the mathworld link above if you haven't already.) Therefore we finally obtain
$$
\vec{a}\times\vec{b} = -ab\sin\theta\vec{e}_\phi
$$
as claimed.
Now to compute $\vec{a}\times\vec{a}\times\vec{b}$, we know that $\vec{a}$ and $\vec{a}\times\vec{b}$ are perpendicular, so they span a rectangle. Therefore the area they span is the product of their lengths, or $a^2b\sin\theta$. (And there is a minus sign from the previous computation.) For the direction we need to compute
$$
\frac{\vec{a}}{\|\vec{a}\|}\times\vec{e}_{\phi}.
$$
$\vec{e}_\phi$ is the vector lying in the $xy$-plane perpendicular to $(1,\pi/2,\phi)_{\text{rec}}$. To be perpendicular to this and $\vec{a}$, we must find the vector in the plane perpendicular to $\vec{e}_\phi$ which, if you draw a picture, you'll see is the one containing $\vec{a}$ and the $z$-axis. Therefore to find the perpendicular we just have to shift $\theta$ by $-\pi/2$ (the sign comes from the right-hand rule). Therefore
$$
\frac{\vec{a}}{\|\vec{a}\|}\times\vec{e}_{\phi} = (1,\theta-\pi/2,\phi)_{\text{sph}}
$$
and if we work this out in rectangular coordinates,
$$
(1,\theta-\pi/2,\phi)_{\text{sph}} = (\sin(\theta-\pi/2)\cos\phi,\sin(\theta-\pi/2)\sin\phi,\cos(\theta-\pi/2))_{\text{rec}} = (-\cos\theta\cos\phi,-\cos\theta\sin\phi,-\sin\theta)_{\text{rec}} = -\vec{e}_\theta.
$$
So putting everything together,
$$
\vec{a}\times\vec{a}\times\vec{b} = -a^2b\sin\theta(-\vec{e}_\theta) = a^2b\sin\theta\vec{e}_\theta.
$$
This is never zero except in the following cases (which are not mutually exclusive): if $\vec{a}=0$, if $\vec{b}=0$, or if $\vec{a}$ and $\vec{b}$ point in the same or opposite directions (so that $\sin\theta=0$). Which you could guess from the original working definition of the cross product: since $\vec{a}\times\vec{b}$ always points perpendicular to $\vec{a}$, as long as we don't have some trivial case the vectors $\vec{a}$ and $\vec{a}\times\vec{b}$ will span a parallelogram of nonzero area.
As you can see, this whole business with spherical coordinates is rather cumbersome for the cross product. This is because the cross product is designed to respect linear combinations, and therefore it works well in a rectangular system where the local geometry looks the same everywhere. However, in curvilinear coordinates (like spherical), vectors do not add coordinatewise like in rectangular coordinates, so the cross product cannot use the special linear structure of $\mathbb{R}^3$. The easiest way to do things is to learn to break up vectors into the local basis for spherical coordinates, and learn the formulas for the cross product of the local orthonormal basis in spherical coordinates. Either that, or as Griffiths suggests in Introduction to Electrodynamics, just convert to rectangular coordinates and try to do most things there.
Best Answer
$\vec{a}=(2, -4, 3), \vec{b}=(-4, 8, -6)$ are elements of $\Bbb R^3$. Notice that $\vec b = -2\vec a$, thus the two vectors are collinear. So the space of vectors that are orthogonal the both of these vectors will just be the space of vectors orthogonal to the line that passes through both of them. Can you see that this space will be a plane?
So you just need to specify a plane with a vector equation. The vector equation of a plane is $\vec r(s,t) = \vec us + \vec vt + \vec c$.
We just need to find any two non-collinear vectors orthogonal to $\vec a$ or $\vec b$ (any we find orthogonal to one will automatically be orthogonal to the other).
So we need $(x,y,z) \cdot (2,-4,3) = 2x-4y+3z=0$. Being a linear equation in three variables, we should just be able to choose two of the variables and solve for the last (though don't choose them both zero or you'll just end up with the zero vector which is collinear with every other vector). Let's choose $x=3$ and $y=0$. Plugging in, we see that $z=-2$. So one vector orthogonal to $(2,-4,3)$ is $(3,0,-2)$. Now let's choose $x=0$ and $y=3$ (You could choose the the two numbers to be whatever you like, but notice I chose them so that I'd get integer solutions because no one likes unnecessary fractions). Then $z=4$. So another vector orthogonal to $(2,-4,3)$ is $(0,3,4)$. Notice that $(3,0,-2)$ and $(0,3,4)$ are not collinear (they are not scalar multiples of each other).
So let $\vec u=(3,0,-2)$ and $\vec v=(0,3,4)$. Then to find $\vec c$ we need any point on the line $\operatorname{span}(2,-4,3)$. $(0,0,0)$ is in that span. So let $\vec c = \vec 0$.
Then the equation representing our plane -- and thus every vector orthogonal to $\vec a$ and $\vec b$ -- is just $$\vec r(s,t) = (3,0,-2)s + (0,3,4)t$$