Preliminaries
To set the stage, I'll address a couple of preliminary issues first, and then I'll answer the numbered questions Q1-Q4.
A fundamental assumption is that the eigenvalue-spectra ... of $H$ and $H_0$ coincide. Although this is mysterious to me, I can accept this.
From the context, I suspect that Weinberg (reference 1) might be using the word spectrum with a nuance that exceeds its standard meaning in the mathematical literature, implying something about the states as well as about the spectrum itself, but I'll explain why the statement is true if we define spectrum in the standard way. Namely: the spectrum of an operator $H$ is the set of complex numbers $z$ for which $H-z$ is not invertible (reference 4). Suppose that
The spectrum of $H$ has a gap, meaning that all states are separated in energy from the vacuum by a finite gap $\geq M$.
The model whose Hamiltonian is $H$ has at least one family of single-particle states among which the energy can be arbitrarily close to $M$.
Then $H$ and $H_0$ definitely do have the same spectrum. This is clear because $H_0$ is defined to have the same single-particle states as $H$, and because single-particle states can have arbitrary energy $>M$ if the lower bound is $M$. Therefore both $H$ and $H_0$ have the spectrum $\{0\}\cup (M,\infty)\subset\mathbb{R}$, no matter what the multi-particle states look like.
But here's the important point, which might relate to what Weinberg really meant by spectrum: equality of the spectra (with the standard definition I used above) does not imply the existence of multiparticle states satisfying Weinberg's equation (3.1.12). The real justification for (3.1.12) is that in QFT, if single-particle states exist, then we can also construct multi-particle states in which the particles are so widely separated that they might as well be non-interacting. As they get farther away from each other (in the infinite future or infinite past), we can take them to approach energy eigenstates. For a more careful treatment of this, see theorem 4.2.1 in reference 2.
I presume that we can not write any $\newcommand{\cH}{\mathcal{H}}\Psi\in \cH$ in this way, otherwise we would simply have $\cH\simeq \cH_0$, which is of course trivial, right?
The Hilbert spaces $\cH$ and $\cH_0$ are isomorphic ($\simeq$) to each other, of course, regardless of the Hamiltonians $H$ and $H_0$. You're really asking whether they're equal to each other (whether the subset $\cH_0\subseteq\cH$ is all of $\cH$). Well, the operators $H=H_0+V$ and $H_0$ both act on $\cH$, and since $H_0$ is a free-field theory, we know that its "in/out states" do span all of $\cH$, so $\cH_0=\cH$.
I'm not sure what you were getting at with "...which is of course trivial, right?" but I'll add this comment just in case. A Hilbert space has no physical significance by itself. It's just a vector space over $\mathbb{C}$ with an inner product, satisfying some conditions. In quantum physics, a model (or theory) is a Hilbert space together with a map that says which operators represent which measurable things. Example: QCD and nonrelativistic single-particle QM are wildly different models, but their Hilbert spaces are isomorphic to each other. I wrote another answer to help clear this up, because sometimes people say Hilbert space when they really mean model (or theory).
Question Q1
According to page 3 in reference 3, this hasn't been strictly proven one way or the other. One difficulty is that the interaction $V$ can't be neglected when the $H$-particles are close together, and $\cH_0$ includes states in which the $H_0$-particles are close together. In leiu of a proof, I'll give a heuristic argument.
In a theory with no interactions, even if we started with a state with $N$ particles sitting right on top of each other, dispersion (because of the usual "uncertainty principle") would eventually make their wavefunctions spread out so thinly that the state is well-approximated by a superposition of states in which the particles are all far away from each other.
Now consider the interacting theory, with Hamiltonian $H$. Start with an arbitrary state $\Psi$ and consider what happens in the infinite past/future, like in your Q3. Heuristically, we expect the same thing to happen. The possibility of bound states is not a problem, because if some of the particles remain permanently bound together, then we have already included that bound state as one of the things we're calling a particle in $\cH_0$.
Altogether, this suggests that even though we started with an arbitrary state $\Psi$, it asymptotically (in the past/future) approaches a superposition of states in which all of the particles are widely separated. If this heuristic argument is correct, then the answer to question Q1 is yes.
Question Q2
Same answer as Q1.
Question Q3
If the answer to Q1 really is yes, then we can expand any state $\Psi$ in terms of either in-states or out-states. Expanding it in terms of in-states (respectively out-states) is more useful if we want to consider observables that are well-localized in the distant past (respectively future), like you suggested. I don't know how this can be "seen from (3.1.12)" by itself, but it can be seen from my heuristic answer to Q1.
Question Q4
Weinberg says we don't, not that we can't. His statement is merely meant to remind us that he's using the Heisenberg picture.
Weinberg (1995), The Quantum Theory of Fields (Volume I: Foundations) (Cambridge University Press)
Haag (1996), Local Quantum Physics (Springer)
Buchholz and Summers (2005), Scattering in Relativistic Quantum Field Theory: Fundamental Concepts and Tools (https://arxiv.org/abs/math-ph/0509047), which was brought to my attention by another answer
Page 6 in Murphy (1990), $C^*$-Algebras and Operator Theory (Academic Press), and also page 180 in Debnath and MikusiĆski (2005), Introduction to Hilbert Spaces with Applications (Academic Press)
Best Answer
Let me clarify the confusion regarding the Heisenberg picture and time evolution. In Schrodinger picture, states evolve with respect to time. But in the Heisenberg picture states don't evolve with respect to time. In a coordinate system $(t,x^i)$, you choose let us say the state $|\psi(t=0)\rangle$ in the Schrodinger picture as your state $|\psi\rangle$ in the Heisenberg picture. But in another coordinate system $(x^{i},t^\prime=t+\tau)$ you have the state $|\psi(t^\prime=0)\rangle=|\psi(t=-\tau)\rangle$ as the state in the Heisenberg picture. i.e. In the Heisenberg picture, in one frame the state is $|\psi\rangle=|\psi(t=0)\rangle$, in a time translated frame with $t^\prime=t+\tau$, the state is $|\psi^\prime\rangle=|\psi(t=-\tau)\rangle$. Therefore if we apply a "time translation" operator on a state in the Heisenberg picture going from one frame to another, it is equivalent to doing a time evolution in the Schrodinger picture in a given frame. Weinberg clearly mentions that he is doing a time translation and not time evolution.