Having read numerous texts in this space, I would highly recommend R by example.
The text has a very broad overview of various statistics concepts, and how to run examples in R. And I agree with Hans post, that a good approach is to tackle both R and Statistics with texts geared towards both.
A more formal text would be Discovering Statistics Using R. While less broad in scope than "R by example", it has a more formal and explanatory approach to many of the core concepts of statistics using R.
However, keep in mind both of the above texts are more geared towards statistics; not machine learning.
There are several good books more dedicated to machine learning, but less dedicated to some of the statistical concepts you describe (like markov chains).
Several good R cookbooks that have more of a coding/machine learning emphasis and more of a hands on applied approach to using R for machine learning are available. Among them, R Cookbook, R in action, and Machine Learning for Hackers are all very good.
A more recent text that is very good at practical examples for ML/data mining is Data Mining and Business Analytics with R; it is a bit costly, but one of the best practical example books (specifically dedicated to data mining/machine learning) I've come across.
Lastly, a more recent book in the cookbook space that is good is Machine Learning with R. It is very dedicated to ML and R examples, while being a more gentle introduction suitable for those with a programming background.
While Elements of Statistical learning is a great text, I really wouldn't recommend it as an introduction to the field. There is a more recent text by the authors, with a less rigorous introduction, An Introduction to Statistical Learning: with Applications in R. The 2nd text has numerous computational examples to reproduce.
Seeing as you've had prior coursework in statistics, I don't think any of recommendations are too advanced. However, the "Naked guide to statistics," is more of a layman's general audience non-fiction book describing Statistics. And the second book, as far as I know, lacks R, and is likely too broad and dense with sparse examples (haven't read it though).
You can preview many of the books on amazon (7 days) or portions on google books, to see if they are suitable to you.