We prove central limit theorems, Berry-Esseen type theorems, almost sure invariance principles, large deviations and Livsic type regularity for partial sums of the form $S_n=\sum_{j=0}^{n-1}f_j(...,X_{j-1},X_j,X_{j+1},...)$, where $(X_j)$ is an inhomogeneous Markov chain satisfying some mixing assumptions and $f_j$ is a sequence of sufficiently regular functions. Even though the case of non-stationary chains and time dependent functions $f_j$ is more challenging, our results seem to be new already for stationary Markov chains. They also seem to be new for non-stationary Bernoulli shifts (that is when $(X_j)$ are independent but not identically distributed). This paper is the first one in a series of two papers. In \cite{Work} we will prove local limit theorems including developing the related reduction theory in the sense of \cite{DolgHaf LLT, DS}.