Yes, it is possible and actually very normal to do. Many tourists in Russia will first get a cheap "sponsor" to provide a letter of invitation. A cheap sponsor could be a tourist company or a hotel. It is normal for people to get their visa granted, and then totally change their hotel plans after it is issued. You do not need to enter Russia to change your hotel plans.
You must register at any hotel you stay at.
Russian Consulate's Visa Registration information section:
Travelers who spend more than seven days in Russia must register their visa and migration card through their sponsor (at the local Federal Migration Service (FMS)) or landlord (at the local post office or FMS). Travelers staying in a hotel must register their visa and migration card with their hotel within one day. Even travelers who spend less than seven days in one place are encouraged to register their visas. If a traveler chooses not to register a stay of less than seven days, he or she is advised to keep copies of tickets, hotel bills, or itineraries in order to prove compliance with the law.
U.S. citizens should be aware that Russian police officers have the authority to stop people and request their identity and travel documents at any time, and without cause. Due to the possibility of random document checks by police, travelers should carry their original passports, migration cards, and visas with them at all times.
Rules for registration of foreigners in the Russian Federation changed in January 2007. Registration is now performed either by the traveler’s visa sponsor, or by a hotel, landlord, employer, or other entity acting as an “acceptance agent.” The registration application form is called Uvedomleniye o Pribytii Inostrannogo Grazhdanina v Mesto Prebyvaniya and is available at post offices and on the website of the Moscow City FMS at http://www.fmsmoscow.ru/docs/migration_registration/registration.html.
The registration form consists of two parts. The first, top part is filed by the sponsor or acceptance agent with the FMS. The smaller bottom part remains with the traveler, who returns the form to the airport passport control officer upon departure. The last requirement is not enforced strictly. Failure to return the form does not interfere with departure. The process must be repeated if a foreigner travels to a different region of Russia for more than seven days. The registration fee is set and is usually posted in post offices and migration offices. There is a surcharge if the form is mailed. The registration rules are posted in Russian on http://www.fmsmoscow.ru/docs/migration_registration/registration.html
If you stay anywhere shorter than 7 days, you do not need to register. For instance, I went to Moscow for my brother in law's wedding, but was only there for 2 days. I did not register anything. We left for Greece for a week, then came back to Moscow for a few more days. I did not register then either, as I left Russia and went back to the USA. I never stayed 7 consecutive days, so I avoided registration entirely. I also did not stay in a hotel. A hotel makes the registration process very easy, whereas staying with my in-laws would require a trip to the local post office and waiting in line for over an hour to register. Not fun.
It is usually easier to have a hotel do your registration, as they are familiar with the process and usually have English speaking people to fill it out for you, plus they have all the necessary forms, stamps and paperwork support. You simply just sign the forms after they stamp them and keep them in your passport. Do not lose those forms! I have never been asked to produce them, but it could happen and is perfectly legal for the Russian authorities to request it without notice. I usually keep a low profile and keep my English speaking to a minimum, to avoid any checks like that.