Let me comment on your second question:
When we don't know what the Lagrangian is, do we have to just guess and hope it is compatible with the dynamical equations we had already?
If you want the variational derivative of your Lagrangian to yield your equations of motion (or a system which is equivalent to your equations of motion) you should solve the inverse problem of calculus of variations (googling will land you plenty of references; for the "mechanical" case which is apparently your primary interest, you can start here); see also this book by Ian Anderson and Gerard Thompson). In general, there are certain necessary conditions for your equations of motion to satisfy in order that the Lagrangian exists at all. If these are satisfied, finding the Lagrangian $L$ essentially boils down to using an appropriate homotopy operator to reconstruct $L$ from its variational derivative, see e.g. Ch. 5 of the book Applications of Lie groups to Differentail Differential Equations by Peter Olver.
As a historical remark, it is interesting to note that one of the first Fileds medalists, Jesse Douglas, has made significant contributions to this field of research.
Sorry for being rather sketchy, maybe I'll expand this answer a bit later.
