If you speak some Russian then I would feel comfortable in not having reservations outside of Moscow/St Pete.....I'd definately have some reservations for those two cities as hotels are generally expensive and at times extremely expensive.
In the other cities you mention - IF you can get by with some Russian the worst case scenario is renting a flat from someone. Several times in Russia I've been approached by older women at train stations offering to rent a flat.....BUT YOU WILL NEED TO KNOW SOME RUSSIAN TO KNOW THATS WHAT THEY ARE OFFERING!!!!
Personally I'm much less worried about registration in Russia with the new procedures that are now in place. I make it a point to stay at a "western" hotel the first couple of nights and beyond that I'm not concerned. Now that there is no paperwork to be taking around there is less of a risk of police/officials stopping you and giving you a hard time about your registration and whether or not it was done properly - the other thing I don't miss are the guys in some of the smaller interior airports that used to try to get money by questioning the validity of registrations in their OWN CITY!!! - Now there is nothing for them to look at or point to.
Part of the answer to your question comes down to age and how comfortable you are with "bumming around"....no reservations means that there is a chance you sleep in a train station or in a really bad cheap soviet hotel near a train station (and I've seen a few that you'd probably not believe :) )
In terms of planning your trip and train tickets don't discount using some of the independant people that offer services to travellers in the different cities - you find many with personal websites and often will handle some of those type of things for reasonable fees (like $10 to book a few train tickets) - just use common sense and don't Western Union off a bunch of money to someone.
Enjoy your trip - Russia is an interesting country to visit.