Is strain always relative to some initial state? Let us say I am given a material with no knowledge about its history. Can I somehow calculate its strain ? Or a strain is always relative to some initial state (change in length/initial length) ?
 A: Strain is not a "thing" for a material. Saying that a material "has strain" seems wrong. It's not a property of the material like volume or temperature etc.
Strain is different for each process. It depends on the process or initial state. Without knowing what has happened with a material, you can only guess the  strain it has experienced from looking into how the microstructure is distorted. 
This of course still depends on how the microstructure looked before the strain started. Yes, knowledge of the history is necessary, and you need to define what your starting point is. 
A: As stated by Steeven, strain is not a property of a material. Instead, strain is something you do to an object … just like rotation is not a property of an object, but is an action you do to an object.
In fact in 3d space (ie: x,y,z), rotations and strains form the group GL(3,R).  This is the group of all invertible 3x3 matrices M of real numbers. 
We can describe what these transformations do by just talking about the matrices $M$ that are very close to the identity matrix, where all elements in the matrix $\Theta$ are <<1. All these elements are in radians.
$$ 
M=I+\Theta
$$
$$
\Theta = \begin{bmatrix}
           0 & \theta^{12} &-\theta^{13} \\
-\theta^{12} &           0 & \theta^{23} \\ 
 \theta^{13} &-\theta^{23} &           0  \\
\end{bmatrix}_{Antisymmetric}
\
+ \begin{bmatrix} 
\epsilon^{11} & \epsilon^{12} & \epsilon^{13} \\
\epsilon^{12} & \epsilon^{22} & \epsilon^{23} \\
\epsilon^{13} & \epsilon^{23} & \epsilon^{33} \\ 
\end{bmatrix}_{Symmetric}
$$
By taking products of these matrices we build all the matrices $M$ in the group for any size elements in $\Theta$.
$$
M=e^{\Theta}=I+\Theta+\dfrac{\Theta^2}{2!}+ \dfrac{\Theta^3}{3!}+ \dfrac{\Theta^4}{4!} +…
$$
The $\theta$ are antisymmetric, make M orthogonal ($M^T =M^{-1}$), and leave the length  ${x_1}^2 + {x_2}^2+{x_3}^2$ invariant.  Because lengths are invariant, the transformations are called rotations.  The $\epsilon$ do not leave lengths invariant and are called strains.
The parameter $\theta^{12}$ means rotate the object about axis1 X axis2.  That is, put your right thumb perpendicular to the plane formed by axis1 and axis2, such that you fingers would push axis1 into axis 2.  Then in this same rotation direction about your thumb rotate the object by $\theta^{12}$ radians.
The parameter $\epsilon^{11}$ means stretch the object by $(1+\epsilon^{11})$ along axis1.
The parameter $\epsilon^{12}$ means parallelepiped the object in the plane containing axis1 and axis2.  For example, a square box with its sides initially along axis1 and axis2, becomes a parallelepiped with its sides tilted inward from axis1 and axis2 and its diagonal from the origin stretched.  Both sides now make inward angles of $\epsilon^{12}$ radians with their respective axis1 or axis2.
Examples of large rotation and strain matrices are:
Rotate about axis3 by $\theta^{12}$ radians.
$$
M(\theta^{12})=\begin{bmatrix} cos(\theta^{12})  & -sin(\theta^{12})  & 0 \\ sin(\theta^{12})   & cos(\theta^{12})  & 0 \\ 0 & 0 & 1 \end{bmatrix}
$$
Strain (parallelepiped) about the axis3 by $\epsilon^{12}$ radians.
$$
M(\epsilon^{12})=\begin{bmatrix} cosh(\epsilon^{12})  & sinh(\epsilon^{12})   & 0 \\ sinh(\epsilon^{12})   & cosh(\epsilon^{12})  & 0 \\ 0 & 0 & 1 \end{bmatrix}
$$
Strain (stretch) along the axis1 by $\epsilon^{11}$ radians.
$$
M(\epsilon^{11})=\begin{bmatrix} e^{\epsilon^{11} } & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}
$$
Notice that for $\epsilon^{11}<<1$, the fractional change of the length of an object in the 1 direction is $\epsilon^{11}$.
If you now consider GL(4,R) (ie: 4x4 matrices) acting on (x, y, z, t), the parallelepiped strains ($ \epsilon^{14}, \epsilon^{24}, \epsilon^{34} $ and their associated cosh’s and sinh’s you may recognize as the Lorentz Boost Transformations of Special Relativity.  The Lorentz Boosts are really just space-time strains !
Interestingly there are also space-time rotations ($ \theta^{14}, \theta^{24}, \theta^{34} $) and their associated cos’s and sin’s.  Products of the other GL(4,R) transformations (for which there are physically identifiable processes that do them) will give these so these space-time rotations must exist, but how do you directly do them.  Space-time rotations are weird (and seemingly impossible) because they can take a time like coordinate (t>x) and rotate it into a space like co-ordinate (x>t) and vice-versa.
