With what we know about physics, is it possible that when the universe 'began', around when quarks and leptons were produced, another particle, which doesn't couple to either quarks, leptons or photons was also produced ? The only other way that we can observe its existence is via the effects of its gravitational field. In others words, some ''dark-matter-particle'' that doesn't interact with known forms of matter, except through gravity?
Yes, there have been suggestions that such particles exist, and an example is the sterile neutrino.
But your question is a little more involved than you might think at first sight. For example if the sterile neutrino only interacts through gravity what interaction caused it to be created in the first place? There is nothing in the Standard Model that could create such particles. However we expect that the Standard Model is a low energy approximation and as we work backwards in time towards the Big Bang and the energies get higher we'll need a grand unified theory like SO(10) and ultimately a quantum theory of gravity (which may or may not be String Theory). These contain interactions that can create particles like sterile neutrinos. However this remains a speculative area of Physics and at the moment we can't say definitely whether such particles exist or if they exist how they were created.
This answer is within the current physics and theoretical understanding, which has developed a successful formalism that includes all the experimentally seen particles in the Standard Model. The model has been very successful in predicting several new particles using its symmetry and mathematics, the experimental observation of the Higgs boson serving as perhaps the last point of validation.
This model does not include gravity and theorists are working hard to form a model that will encompass the standard model's $SU(3) \times SU(2) \times U(1)$ group structure, in more complicated models that include the quantization of gravity. String models promise to be able to do so but the theories have not advance to the point of proposing a solid model from the thousands of possibilities. Once such a model is proposed it can be checked on whether there exist predictions for particles that to first order interact only with the gravitational field.
There are proposals to see the results of graviton resonances at the LHC, and it might be that in some string model a first order stable or long living gravitation only particles will appear in the final formulation. Certainly though the particle would interact in higher orders with other particles within the standard formulations of the theory.
Let us clearly draw the line between two things here, since the question can easily involve opinion based answers, which may also be dubbed non-mainstream (which isn't welcome on this site).
1) The existence of dark matter is generally believed by a majority of the Physics community, since astronomical observations, notably by the Planck space observatory, suggest that visible matter makes up only $\sim 5 \%$ of the total mass energy of the universe. Most conveniently, that means that some matter isn't visible to us, hence we call it 'dark', and look at extensions of current theoretical frameworks to account for them, as John and Anna have mentioned in their answers.
However, there are alternatives, which are intended towards accounting for these observations without including any extra invisible matter, such as the Modified Newtonian Dynamics Approach. If this is proved correct with time, we won't need to worry about the dark-matter particles you are asking about. The final answer is really far off, since neither of these mentioned approaches can claim to be the final word on this subject.
2) Regarding ''Dark Matter Particles'', as dmckee mentions in a comment, one can't be absolutely sure as to how to look for them with the current set of theoretical understanding, yet I am aware of certain experimental groups having reported measurements relating to WIMPs, such as the widely popularized Super Cryogenic Dark Matter Search (SuperCDMS) experiment. The strategy here is to measure the recoil energy of a nucleus in a Nucleus-WIMP collision, which is more or less a direct detection as compared to the indirect method - analyzing the debris in WIMP decays or annihilations. They had reported some measurements, at roughly $3\sigma$ level, which are encouraging signs, though not conclusive yet. (An alternative reference can be found here ). (Sidenote - The trust level is a little higher than $3\sigma$; nobody believed the Higgs boson ''discovery'', till a $5\sigma$ measurement was reported.)
A completely consistent theory of their genesis, is an issue that can be settled only after we know for sure that they exist. Right now, neither the theoretical nor the experimental status of this problem can warrant that. Or worst case, if MoND works out fine, we may not even need them. Only time will tell.