Does the Hilbert space include states that are not solutions of the Hamiltonian?
It is the algebra of observables that determines its possible representations, i.e. the corresponding hilbert space(s).
The Hamiltonian describes the dynamics, within the given representation.
Edit. To clarify a little bit, the common mathematical description of quantum mechanical systems is the following.
The (bounded, complex) observables of a quantum system form an involutive Banach algebra called a C*-algebra. This structure allows for the observables to be added ($+$), multiplied ($\cdot$), adjoined ($^*$) in a closed way; and gives a meaning to the "magnitude" or norm of a given observable. The true physical observables are the self-adjoint elements of the C*-algebra $\mathfrak{A}$ that satisfy $a^*=a$ (and thus have real spectrum). The quantum states are the positive-preserving objects of the topological dual $\mathfrak{A}^*$ with norm one.
A common example of C*-algebras are the algebras of bounded operators on Hilbert spaces. It turns out that every C* algebra is an algebra of operators on some Hilbert space:
Theorem [Gel'fand]. Every C* algebra is *-isomorphic to an algebra of bounded operators on some Hilbert space.
Therefore as long as the quantum bounded observables are described by a C* algebra, they are representable as operators on some Hilbert space. Of course that representation is not unique; for every state $\omega\in\mathfrak{A}^*_+$, there is an associated representation $(H_\omega, \pi_\omega,\Omega)$ given by the so-called GNS construction. In addition, the aforementioned representation is irreducible only if the state $\omega$ is pure.
Said that, the next question may be the following. Are all the irreducible representations of a given algebra unitarily equivalent? (i.e. are all the representations roughly speaking equivalent up to a change of basis?) If the answer was affirmative, this would in some sense tell us that the Hilbert space associated to a given algebra of observables is unique. The answer, however, is in general no; a very important example given by the algebra of canonical commutation relations of (free) quantum field theories. In the case of quantum mechanics instead, every irreducible representation of the algebra of canonical commutation relations is unitarily equivalent to the usual Schrödinger representation.
The Hamiltonian is partly unrelated to that. It is the generator of the quantum dynamics $(U(t))_{t\in\mathbb{R}}$, and of course the latter should act on the algebra of observables (equivalently, on states). Suppose that the given algebra of observables is $\mathfrak{A}$, the evolution should be a group of automorphisms on the algebra with some suitable continuity properties with respect to the time $t$. However, in many concrete applications we have to consider a big enough algebra of observables for that to be possible with an evolution that matches the requirements we want (e.g. given by observations on the system). The algebra of canonical commutation relations $\mathrm{CCR}$ may not be enough, and in order to enlarge it we can for example fix an irreducible representation $(H,\pi)$ such that $\pi(a)\in\mathcal{L}(H)$ for any $a\in\mathrm{CCR}$ is a bounded operator. The bicommutant $\pi(\mathrm{CCR})''$ of the algebra of canonical commutation relations in the representation $\pi$ contains $\pi(\mathrm{CCR})$ and consists of all bounded operators on $\mathcal{L}(H)$ that commute with all operators that commute with all operators in $\pi(\mathrm{CCR})$ (and it is a C* algebra). On such bicommutant, or more generally on $\mathcal{L}(H)$, it may be possible to define the unitary evolution $(U(t))_{t\in\mathbb{R}}$ and its generator, the Hamiltonian. This Hamiltonian is, however, representation dependent (with repsect to the canonical commutation relations) because in general $U(t)[\pi(\mathrm{CCR})]\not\subset \pi(\mathrm{CCR})$.
There is a certain subtlety to your question.
For quantum systems with a finite number of degrees of freedom, as commonly dealt with in intro QM, things are relatively simple:
Yes and no: the Hamiltonian certainly determines a basis for the Hilbert space of states, but the working Hilbert space depends on the domain of definition of the problem and on associated boundary conditions. See particle in a 3D-box vs. free particle on the entire 3D-space, as well as particle in a box with Dirichlet b.c.-s vs. particle in a box with periodic b.c.-s, etc. Alternatively, the Hilbert space is determined by the algebra of system observables, as pointed out in user1620696's answer, but the two descriptions are eventually equivalent. Moreover, there exists an even deeper equivalence of Hilbert spaces, see point(3) below.
Each particle lives in its own Hilbert space, but the combined interacting system lives in the direct product of individual Hilbert spaces. Again, see relation to algebra of observables as in user1620696's answer.
Leaving aside spin and the spin interactions mentioned by Hosein, generally no, for a finite number of degrees of freedom the Hilbert space does not change under perturbations. According to the Stone-von Neumann theorem, in this case all possible Hilbert spaces are isomorphic to one another (or equivalently, there is a unique irreducible representation of the canonical commutation relations), hence distinguishing one over the other makes no formal difference. At most, the total Hilbert space decomposes into a direct sum of multiple isomorphic copies.
For systems with an infinite number of degrees of freedom, which are the domain of Quantum Field Theory, points (1) and (2) above remain largely valid, but the situation does change drastically in regards to point (3).
The Stone-von Neumann theorem does not hold for quantum fields, and one may find that certain unitary transformations defined on one Hilbert space, constructed around a given Hamiltonian, produce states that are orthogonal to that whole Hilbert space and living in an entirely new, inequivalent state space. This is the case of inequivalent vacua of many QFT Hamiltonians, from condensed matter ones (see boson condensation, superconductivity, etc.) to QCD.
Further, the nature of such inequivalent vacua (or better say, unitarily inequivalent representations of the dynamics) is determined by the nature of interactions between free-fields described by some free-particle Hamiltonian and corresponding state space.
For an idea of what is going on, see for instance Sec. 1.2 of this review on Canonical Transformations in Quantum Field Theory.
The point is that one first should identify the Hilbert space of a system, then writes its Hamiltonian. In ordinary problems it's easy to define the proper Hilbert space and one writes the Hamiltonian without spending time finding the Hilbert space. for example, one particle without spin. So when you write a Hamiltonian you should know the Hilbert space first.
One more point: sometimes people don't know the structure of the Hilbert space of a problem, they just write a Hamiltonian by guessing and then try to figure out the structure of the Hilbert space, one example is the quantization of free fields which turns out to give the Fock space-the direct sum of zero, one, two, $\dots$ particle states.
So the answer to your questions is:
Yes, in the sense that its eigenvectors are a basis of a Hilbert space, but whether this Hilbert space is convenient for describing your system which you want to build a model of or not is another story.
No, only if they are completely independent and there is not any interaction between them, then each one has its own Hilbert space. Nevertheless you can write a Hamiltonian for both these two particles by a tensor product.
As I said, if you have defined the Hilbert space, then each term in the Hamiltonian should be a well defined operator on that Hilbert space. But if you haven't defined the Hilbert space first, then yes the Hilbert space can be changed by adding new terms to the Hamiltonian. For example by adding a term which depends on the spin of particle to the Hamiltonian of a spinless particle which only depends on position and momentum operators.