We study the asymptotic behaviour of Markov chains \((X_n,\eta_n)\) on \(\mathbb{Z}_+ \times S\), where \(\mathbb{Z}_+\) is the non-negative integers and \(S\) is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of \(X_n\), and that, roughly speaking, \(\eta_n\) is close to being Markov when \(X_n\) is large. This departure from much of the literature, which assumes that \(\eta_n\) is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for \(X_n\) given \(\eta_n\). We give a recurrence classification in terms of increment moment parameters for \(X_n\) and the stationary distribution for the large-\(X\) limit of \(\eta_n\). In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between \(X_n\) (rescaled) and \(\eta_n\). Our results can be seen as generalizations of Lamperti's results for non-homogeneous random walks on \(\mathbb{Z}_+\) (the case where \(S\) is a singleton). Motivation arises from modulated queues or processes with hidden variables where \(\eta_n\) tracks an internal state of the system.