"Inverse" Helmholtz Decomposition

If ${\bf F} = - \nabla \phi + \nabla \times {\bf A}$, we get $\nabla \cdot {\bf F} = - \Delta \phi$. So we want to get $\phi$ by solving a Laplace equation. Then we get $\bf A$ by solving $\nabla \times {\bf A} = {\bf F} + \nabla \phi$.

In your first example, ${\bf F}_1$ is indeed divergence-free, so you can take any $\phi$ whose Laplacian is $0$. You could take $\phi = 0$, but if you prefer you can use any harmonic function. For example, let's take $\phi = x$ which makes $\nabla \phi = [1,0,0]$. So now you want $\nabla \times {\bf A} = [1-y,x,0]$. One possible solution is ${\bf A} = [xz, yz-z,0]$. There are many possible solutions: the decomposition is far from unique.

First of all, the wrong thing that you think is wrong, is totally wrong! :) So, yes, you are right!

If you take the divergence and curl of the following equation

$$ \textbf{F}=-\nabla \phi+\nabla \times \textbf{A} $$

then you will get, respectively

$$\boxed{ \begin{align} \nabla \cdot \textbf{F} &= - \nabla^2 \phi \\ \nabla \times \textbf{F} &= - \nabla^2 \textbf{A} \end{align} }\tag{1}$$

where use has been made of the identitiy

$$\nabla \times \nabla \times \textbf{A} = \nabla (\nabla \cdot \textbf{A})-\nabla^2 \textbf{A}$$

and the assumption

$$\nabla \cdot \textbf{A} =0 $$

which has been made for simplicity.

In conclusion, for a given vector field $\textbf{F}$, you should solve the Poisson equations mentioned in $(1)$ for $\phi$ and $\textbf{A}$.