How can one know if a theory allow action at a distance effects or not? 1-In general, if a theory has action at a distance effects, where can that appear exactly in the theory?
2-Does it appear in the dynamical law of the theory? (does it appear in Newton's 2nd law? where can it be spotted?) 
3-Does it appear in the force law of the interaction? (it is said that Newton's law of gravitation, $\displaystyle F\sim\frac{m_1m_2}{r^2}$, supports action at a distance effects. How can one see that from the form of the law?)
4-Before special relativity, causality roughly means cases always come before effects. Now if the force law allows action at a distance, as in Newtonian gravity in 3, then the interaction is instantaneous. It seems that the words "before" and "after" lose their meaning in this case, then how causality is defined then?
 A: Take a look at Newton's law in the form of gravitational potential $$\nabla^{2}\phi=4\pi G\rho$$ Let's say we change the mass density of whatever our gravitating object is.  Now, the gravitational field is instantly changed - everywhere, everyone feels a different potential, and a different gravitational force.
Like you said in 3), it also appears in the force law.  Let's say you grabbed one of the masses, and yanked it backwards, increasing the radius.  Even if the other object is on another end of the observable universe, it instantly feels a weaker gravitational force.  This is instantaneous.
4) Right.  Newton himself said the idea that gravity occurred instantaneously everywhere was 'philosophically absurd'.  However, Newton's laws worked excellently to describe the motion of planets, and the trajectory of objects through gravitational fields.  There were some attempts to find a 'speed of gravity' by formulating a more complete theory of gravity, such as Le Sage gravity, but none really caught on.  Of course, this was until general relativity, which solves the problem of gravitational action at a distance. 
A: 1) A theory has action at a distance if there is some form of an effect (e.g. a "force" in the classical sense, or an operator in the quantum sense) that depends on two positions in space.
2) It does appear in the dynamics of the theory.  If the dynamics of a certain point in space depends on some other point in space, then the theory supports action at a distance.  For example, in Newton's Second Law, the force F is caused by some source at point "x" while it causes an acceleration at some receiver at point "y".  Thus we have an effect that depends on two positions in space.
3) The force law of the interaction, as described above in 2) above, does support action at a distance.  When you write F as proportional to 1/r^2, we are actually defining F as a force created by some source at the origin of our coordinate system.  This definition hides the fact that F supports action at a distance (a.k.a. non-locality).  We can remove this hiding by instead writing a more generalized F, in which case it is proportional to 1/(r-r')^2 where r is the position of the receiver of the force and r' is the position of the source of the force.
4)  Just because something is instantaneous doesn't mean you can't define a "before" and "after".  Causality still as meaning here.  For example, we can define "before" by saying that the cause of the force F occurs before the source of the force is created.  Of course, such a thing is not possible because F is instantaneous, but that doesn't mean we can't define the terms.  Really the notion of causality is only useful once you allow for space and time to be mixed together.
There is more physics here then I represented, but hopefully the explanations get to the core of your questions without adding unnecessary complications.
A: No action at a distance means that forces apply only through contact. 
Thus if one models gravitation with the inverse-square law of point masses, one has an action at a distance. 
But if one models gravitation with a relativistic gravitational field generated by extended masses also modeled by a density field then interactions are expressed through differential equations, and the force at any point is determined by these fields in an infinitesimal neighborhood of the point, hence are local. The action at a distance has been replaced by a local action of more complicated objects - the fields. 
Causality (before and after) is completely independent of this.
