The motion-independent definition of force I think we must be able to accomodate a definition of a force on some particle which is independent of the motion of the particle, for all kinds of forces, to surely verify the statement like 'force on a particle equals the time derivative of the momentum of the particle'. Is that true?
I've learned even if we push some particle 'by constant force', the particle's acceleration would be decreasing in time, instead of maintaining some value. This kind of statement would not be verified without its own(in the sense mentioned above) definition of force, right? I used to imagine rather ideally that I would put contracted springs in every point in the particle's trajectory and let them push the particle by same amount of spring's streching in constant frequency, to realize 'the constant force' on moving particle.
 A: The question is, what do you mean by "force"? :)
I mean, what confuses you is probably:  
Why do we call $$F=ma$$ a physical law, if this is the only definition of force?
This is a good thought. But fortunately Newton has not just this one axiom, but two (the historical "first" is a special case of $F=ma$, but there is a third), which are connected. 
So I would put it like this:
If two bodies interact, we call this "exert a force on each other". The result is some change in motion (I will not question the concepts of space and time here, which are necessary for such a statement). And now comes the law (i.e. some nontrivial statement derived from experiment):
The ratio of the accelerations of the two bodies is always the same, and independent of the special type of interaction.
And more than that: this ratio is "transitive", in the sense that the ratio between the bodies A and C is the product of the ratios between A and B and B and C. This step is not self-evident, the ratio could also have been a property of the pair of bodies. But this transitivity allows us to assign a property to each body, that we call "mass".
You see how you need both, the actio=reactio and the acceleration to give those concepts a meaning...?

Well, this mass has no physical meaning so far, only the ratio of masses. We just call some arbitrarily chosen mass one kg.
And now that we know what to call mass, we can define a force by $F=ma$. The value of the force has no meaning at all so far, since we already defined mass with this very equation. To call this concept force gets a meaning later, if we add to this definition (concerning the action of the force) some further formulas about the cause of the force, like Hooke's law or the law of gravitation.

The issue with the relativistic velocities from your second paragraph, 

I've learned even if we push some particle 'by constant force', the
  particle's acceleration would be decreasing in time, instead of
  maintaining some value.

is resolved from this viewpoint. "Constant force" now means, that the reaction on the object from which the force is applied is constant. So this statement says that in non-classical circumstances there are deviations from the abovementioned observation, that the ratio of accelerations depends only on the property "mass" of the two involved objects. But fortunately these deviations occur not randomly but systematically, and the system turns out to be: we can still retain all the above concepts with the addition, that the mass is dependent on the velocity. It's still transitive, so it's still a meaningfull concept. And derived from it, force is meaningfull...
(Actually, force is harder to retain as a concept, since it's not always possible to say, what pair of objects is interacting, you can have interaction with a field also... and then it's maybe better to let it go and use different descriptions of reality :))
A: 
I think we must be able to accommodate a definition of a force on some particle which is independent of the motion of the particle, \emph{for all kinds of forces}, to surely verify the statement like 'force on a particle equals the time derivative of the momentum of the particle'. Is that true?

The quoted statement is not the best formulation to be independently verified because it assumes force is something measured in units of mass $\times$ acceleration but that is not necessary.
I think you want to verify Newton's 2nd law. This states:
The alteration of motion is ever proportional to the motive force impressed; and is made in the direction of the right line in which that force is impressed.
The law, although formulated unclearly, implies that force is something that has direction and magnitude, and is proportional to their product, not necessarily equal to it.
In present-day simple language, it states this:
Acceleration of a body that does not lose or gain parts is proportional to vector sum of external forces acting on the body due to other bodies.
It is difficult to give exact definition of external force in the above statement, because there are many different kinds of forces; there is gravity force, electric force, magnetic force, contact mechanical force, elastic force, surface tension force etc, each being different in its manifestations. All of them, however, have something in common; they are often present even if the body they act on does not accelerate. 
For example, if we place spring on its circular base on the ground, it will remain there at rest, but gravity force acting on it does not stop to exist just because there is no acceleration. It is still there, only counteracted by the contact normal force due to ground. This spring and in general, any body gets deformed when under action of a force at rest. We can measured this deformation and determine this force in units of deformation.
A: The definition ${\bf F} = \frac{d{\bf p}}{dt}$ is valid in all inertial frames (assuming not considering relativity). If you have another inertial frame you can replace ${\bf v}\to {\bf v' = {\bf v} + {\bf v}_0}$, so that ${\bf p} = m {\bf v}\to {\bf p' = {\bf p} + {\bf p}_0}$ and since ${\bf v}_0$ is constant, have $\frac{d{\bf p'}}{dt} = \frac{d{\bf p'}}{dt}$.
