I have to weigh in with a vote for a Romanian 22 trainer. I bought one and I love it! It has given me zero problems and it was cheap. It is very accurate with subsonic and standard velocity loads. It shoots high velocity loads well also but just not the the ultra tiny 1 hole groups that the others give. It opens up a bit with hypervelocity loads but still gives adaquate accuracy. This is with iron sites. They are properly regulated for standard velocity ammo at 25, 50 and 100 yds. and work pretty well.
Purchasing a 22 will allow you to practice a lot and concentrate on getting the fundamentals of marksmanship perfected. You will be less likely to "spray and pray" if you choose a bolt action rather than the semiauto. It will help you conserve ammo and help keep you focused on making that one good shot.
If you purchase a shotgun also check out the used racks at your local gun dealers. You should be able to find a nice Remington or Mossburg for under $200 that will give you a lifetime of service. If you do get a shotgun start with low power, low recoiling loads and work your way up. Jumping right into the heavy recoilng stuff is a sure way to developing bad habits. (flinching, jerking the trigger, etc)
There are plenty of great new and used 22s on the market right now but in my opinion, the Romanian trainer is the best deal going. My Ruger 77/22 is getting very jealous!