Lived in Kazakhstan for seven years. Best way to get around between cities is flying. Quite a few low cost airlines, Fly Arystan and Qazaq Air were decent, Air Astana isn't that expensive either - flights are often at odd times though as the manage the fleet with international destinations. I'd avoid SCAT, has had some historic safety incidents.

Proof of onward travel - it has been asked for, would recommend having it but you may get away without.