What kind of manifold can be the phase space of a Hamiltonian system? Of course it should have dimension $2n$.
But any more conditions?
For example, can a genus-2 surface be the phase space of a Hamiltonian system? 
 A: Richens & Berry [Physica 1D, 495-512 (1981)] give beautiful examples of such systems (with phase-space that is a surface of genus > 1), which they call pseudointegrable; their examples are invariant manifolds of billiards shaped as polygons with rational angles. These systems are interesting because there are two constants of motion, so invariant manifolds are two-dimensional, but they do not behave at all like integrable systems, whose invariant manifolds are tori (i.e., genus-1). The simplest example is a rhombus billiard with two internal angles of 120 degrees and two of 60 degrees. Its invariant manifolds are exactly genus-2 surfaces. The reason why Arnold's theorem (claiming that invariant manifolds of D-dimensional Hamiltonian systems with D constants of motion are D-dimensional tori) cannot be used is because the assumption that two smooth vector fields can be constructed from the two constants of motion breaks down. (The vector fields have singularities at the corners.)
I very much liked the previous answers by JoshPhysics and ACuriousMind.
A: The bible for the mathematical formulation of classical Mechanics, namely Foundations of Mechanics by Abraham and Marsden, defines a hamiltonian system as a triple $(M, \omega, X_H)$ where $(M, \omega)$ is a symplectic manifold, and $X_H$ is the Hamiltonian vector field corresponding to a hamiltonian function $H:M\to\mathbb R$.
Now, are there typically any restrictions, including perhaps topological ones, placed on $M$?  Well, Abraham and Marsden include some that are pretty standard:


*

*$M$ is hausdorff

*$M$ is second countable

*$M$ is differentiable


Aside from these restrictions, the authors (and I suspect this is standard) don't place any more restrictions on $M$.  In particular, there is no reason why you can't consider a manifold $M$ with arbitrary genus.
Note. As pointed out by user ACuriousMind and others, there are toplogical complications resulting from the fact that only certain manifolds admit symplectic structures, so you can't just pick any old (especially higher dimensional) manifold and have yourself a merry time.
However, notice that in the case of $2$-manifolds, there exist surfaces of arbitrarily high genus that admit symplectic structures because of the following sequence of facts:


*

*Every smooth, orientable $n$-manifold admits a smooth, non-vanishing volume $n$-form.

*Therefore, every smooth, orientable $2$-manifold admits a smooth, non-vanishing $2$-form which is also non-degenerate.

*This $2$-form is closed because its exterior derivative is a $3$-form which must vanish in dimension $2$.


Take for example any $n$-fold torus, each of these guys is a smooth, orientable $2$-manifold which therefore admits a symplectic structure, and the genus of each of them is $n$.  The $3$-fold torus is depicted below

A: The phase space is a symplectic manifold, so any manifold $\mathcal{M}$ that admits a closed nondegenerate 2-form is a possible phase space.
Now, what is necessary (or sufficent) for admitting such a form?
First, as you mention, $\mathcal{M}$ must be even-dimensional.
Second, $\mathcal{M}$ must be orientable. Why? Because orientability is equivalent to the existence of a non-degenerate volume form, and the n-fold wedge product of the symplectic form $\omega$ will always provide such a form, so non-orientable manifolds are out.
Third, if $\mathcal{M}$ is compact, it must have also non-vanishing second deRham cohomology, so that there are closed forms which are not exact, of which the symplectic form is then one. Why? Because vanishing cohomology class of the symplectic form would imply vanishing cohomology of the induced volume form, which cannot be.
In this, I have assumed, as some do, that the term manifold already means a Hausdorff, second countable space. I know nothing about whether non-Hausdorff or non-second countable spaces locally diffeomorphic to $\mathbb{R}^n$ can also be symplectic.
