I too have been trying to understand meaning of quantization, and have had similar kinds of questions as you are asking. So I would like to share my own understanding regarding these.
First of all when we encounter problems in classical mechanics, it is almost never that we are given with a symplectic or Poisson manifold, with a smooth Hamiltonian function on it so that all you have to do is to carry out formal well defined mathematical steps to find equations of motion. Usually finding the phase space itself is part of the problem. And in some cases (good examples I think come from field theories) it could be a nontrivial problem.
On the other hand if some mathematician gives you with a classical mechanics problem s/he will at least provide you with the data {Phase space, Hamiltonian}, because mathematically this data is necessary for defining the problem. Here by phase space I mean a symplectic manifold (or may be a Poisson manifold with a given Poisson structure).
Now coming to your questions :
I would first like to ask what is necessary to have a
sympletic/Poisson structure in a classical mechanical system (e.g. an
isolated particle moving on some Riemannian manifold Q). Do we need an
evolution rule to begin with?
If you want to work on $TQ$ ("velocity space") then here too you can work in Hamiltonian (rather than action) formulation, but your symplectic structure here will depend upon Lagrangian. Also this I think would put some conditions (call them conditions A) on Lagrangian so that you can have a "good" symplectic structure on $TQ$ (i.e. a nice Hamiltonian formulation of the problem on $TQ$) . As of now I don't know what these conditions are but it should not be very difficult to find them from expression of symplectic form in terms of Lagrangian.
If, on the other hand, you want to work on $T^*Q$ then here symplectic structure will not depend upon the Hamiltonian. That is why I think people usually study Hamiltonian formulation of classical mechanics on $T^*Q$ rather than on $TQ$ because here symplectic structure is fixed once and for all and thus to study different physical systems you only need to change your Hamiltonian. In order to go from $TQ$ to $T^*Q$ one needs Legendre transformation and for this to be possible Lagrangian needs to satisfy some conditions (I am not sure what (if any) is the relation of these conditions with conditions A mentioned above; though its likely that they are related).
But many books depart from a Poisson manifold $(P,{,})$ and input the
Hamiltonian later, or even suggest it can be a parameter, some
$h\in C^\infty(P,R)$. This suggests that the Poisson structure is, in fact, more
of a kinematic entity, rather than a dynamic one (means it has no a
priori relation with the rule of how the system evolves). Is that
right? On a practical example, how do we even know what the Poisson
structure would be, if we don't even know what are the momenta?
From what we saw above it should be clear that symplectic structure on Phase space $T^*Q$ is independent of Hamiltonian. On $T^*Q$ we know what position is and what momentum is and that is all that's needed to define a symplectic structure.
Also, as I see, the fact that one can use a Poisson manifold also
comes from the fact that a point in phase space will determine the
state (give a solution curve for the motion by initial value
formulation) only if we restric ourselves to evolution equations of
second order, which means some restriction on the Lagrangian, no?
If classical problem is given in Lagrangian formulation then (as mentioned above) there should be some conditions that Lagrangian must satisfy in order for the problem to have Hamiltonian formulation. On the other hand on a phase space mathematically it would be fine to choose any smooth function as your Hamiltonian.
Lastly: For quantization of a Poisson manifold, do we need the
Hamiltonian beforehand? Or: quantization is kinematic or dynamic?
You don't need to know Hamiltonian for quantizing your phase space. Quantization treats all observables on equal footing. However there are some subtleties due to which not all observables may get quantized. So some of the steps of quantization may require you to refer to your Hamiltonian just to make sure that at least your Hamiltonian function can be assigned to a corresponding quantum operator.