There are several equivalent formulations of mechanics, each of which requires us to accept some principle; but we really can take any formulation as fundamental. In this instance, we want to start with Hamiltonian mechanics, possibly building Lagrangian mechanics from it later.
For Newtonian mechanics, our starting principle is Newton's second law; for Lagrangian mechanics, it is the Euler-Lagrange equation or an equivalent stationary-integral principle, for Hamiltonian mechanics, we can use Hamilton's equations. You can write these equations as $\dot{\mathbb{y}}=\Omega\nabla_\mathbb{y} H$, with $\mathbb{y}$ combining $\mathbb{q},\,\mathbb{p}$ into a single vector of which $H$ is a function and $\Omega$ an antisymmetric matrix on the phase space in which $\mathbb{y}$ lives.
Phase space essentially puts the "two types" of coordinates on one footing. The symplectic product $\mathbb{y}^T\Omega \mathbb{z}$ makes it natural to think of the phase space as a symplectic manifold. From this perspective, time derivatives of $q$s can be written in terms of $q$s and $p$s, and the Lagrangian can be defined as $\dot{q}p-H$ written in terms of $q$s and their time derivatives.
See also Chapter 2 of Wald's Quantum Field Theory in Curved Spacetime and Black Hole Thermodynamics.