Hint the norm on $H_1\times H_2$ is given by
$$\|(x_1,x_2)\|_{H_1\times H_2} =\sqrt{\|x_1\|^2_{H_1}+\|x_2\|^2_{H_2}}$$
and under this norm it is easy to check the completeness of $H_1\times H_2$ since having a cauchy sequence $(x^n_1,x^n_2)_n$ in $H_1\times H_2$ will directly implies that $(x^n_i)_n$ is a Cauchy sequence(Why?) in the Hilbert (Complete space ) space $(H_i, \|\cdot\|_{H_i})$ $i=1,2$
because
$$\|x^n_i- x^m_i\|_{H_i}\le \|(x^n_1,x^n_2)-(x^m_1,x^m_2)\|_{H_1\times H_2} \to 0$$
can you proceed form here?
answer 1: I am not exactly sure, what you mean by the "original (algebraic)" tensor product.
Usually, for two Hilbert spaces $ H_1, H_2 $ the algebraic tensor product $ H_1 \otimes_{alg} H_2 $ is the space of all linear combinations of vectors $ \phi_1 \otimes \phi_2 $. As explained in the Wikipedia article, you define an inner product $ \langle \cdot , \cdot \rangle $ on it by
$$\langle \phi_1 \otimes \phi_2, \psi_1 \otimes \psi_2 \rangle := \langle \phi_1 , \psi_1 \rangle_1 \; \langle \phi_2, \psi_2 \rangle_2.$$
Now, $ H_1 \otimes_{alg} H_2 $ with this inner product is not a Hilbert space, since it is not complete. But its completion $ H_1 \otimes H_2 := \overline{H_1 \otimes_{alg} H_2}^{\langle \cdot , \cdot \rangle} $ is a Hilbert space and is called the tensor product Hilbert space.
The space of Hilbert-Schmidt operators $ HS(H_1^*,H_2) $ you mentioned above is isometrically isomorphic to $ H_1 \otimes H_2 $. You may identify all tensor products $ \phi_1 \otimes \phi_2 $ with the map $ x^* \mapsto x^*(\phi_1) \phi_2 $. This map is in $ HS(H_1^*,H_2) $. Taking linear combinations and limits, this identification extends to an identification of $ H_1 \otimes H_2 $ and $ HS(H_1^*,H_2) $, which can be proven to be isometric and isomorphic.
answer 2: For Hilbert spaces of functions, such as $ L^2(\mathbb{R}) $, you would build a tensor product as
$$ L^2(\mathbb{R}) \otimes L^2(\mathbb{R}) = L^2(\mathbb{R}^2), \qquad (\phi_1 \otimes \phi_2)(x_1,x_2) = \phi_1(x_1) \phi_2(x_2).$$
Note that the 2 arguments $ x_1, x_2 $ are different. So rather than multiplying the functions $ \phi_1, \phi_2 $ in an $x$-$y$-diagram, you go to a 3-dimensional $x_1$-$x_2$-$y$-diagram and multiply the functions
$$ f_1(x_1,x_2) = \phi_1(x_1) \; 1(x_2) \qquad \text{and} \qquad f_2(x_1,x_2) = 1(x_1) \; \phi_2(x_2) $$
(meaning $ (\phi_1 \otimes \phi_2)(x_1,x_2) = f_1(x_1,x_2) f_2(x_1,x_2) $).
More generally, $ L^2(\mathbb{R}^n) \otimes L^2(\mathbb{R}^m) = L^2(\mathbb{R}^{n+m}) $ for any $ n,m \in \mathbb{N} $, so the tensor product basically "adds the parameter dimensions of your functions". You may also use other Hilbert spaces, such as $ L^2(\Omega) $ with $ \Omega \subset \mathbb{R}^n $ being a nice set or even the Sobolev spaces $ H^s(\Omega), s \ge 0 $
answer 3: Each Hilbert-Schmidt operator $ K \in HS(L^2(\mathbb{R})^*, L^2(\mathbb{R})) $ can be identified with a kernel $ k(x_1,x_2) $ with $ k \in L^2(\mathbb{R}) \otimes L^2(\mathbb{R}) = L^2(\mathbb{R}^2) $.
That means, for $ \phi^*_1 \in L^2(\mathbb{R})^* $, the function $ K \phi^*_1 \in L^2(\mathbb{R}) $ is given by
$$ (K \phi^*_1)(x_2) = \int_\mathbb{R} k(x_1,x_2) \phi^*_1(x_1) \; dx_1$$
The identification of kernels $ k \in L^2(\mathbb{R}) \otimes L^2(\mathbb{R}) = L^2(\mathbb{R}^2) $ and Hilbert-Schmidt operators is one-to-one. So you may also construct $ L^2(\mathbb{R}) \otimes L^2(\mathbb{R}) $ using Hilbert-Schmidt operators on such function spaces.
Best Answer
A key question here is "What precisely does $H_2\subseteq H_1$ mean"? Let's begin with the identity map on the pre-Hilbert space $H$: $$\text{id}:(H,(\cdot,\cdot)_2)\to (H,(\cdot,\cdot)_1).$$ where we assume that, for all $h\in H$, we have $(h,h)_1\leq (h,h)_2$. This map lifts uniquely to the completions $$i: H_2\to H_1.$$ It is often overlooked, however, that the resulting map $i$ may not be injective. The map $i$ is injective if and only if the bilinear form $((h,h)_2, H)$ is closable on $H_1$.
Let's suppose that $i$ is injective so that we can really think of elements of $H_2$ as also belonging to $H_1$. We should consider $H_2\subseteq H_1$ as shorthand for $i:H_2\to H_1$.
Now $i$ is a linear map, and the dual map gives $i^\prime:H_1^\prime\to H_2^\prime$. This gives a precise meaning to $H_1^\prime\subseteq H_2^\prime$. Combining this with Riesz representations on $H_1$ and $H_2$, we can write $$H_1\overset{j}{\rightarrow} H_1^\prime \overset{i^\prime}{\rightarrow} H_2^\prime \overset{k}{\rightarrow} H_2.$$ I think that this is what you mean by $H_1\subseteq H_2$.
In short, all of the paradoxes disappear when you keep careful track of the mappings involved.