License:
After you have graduated from medical school and taken Steps 1, 2, and 3, you can legally practice medicine and perform any procedure imaginable. However, like njbmd mentioned, you are going to have a tough time getting people to sign up for your neurosurg sessions if you haven't gone through a residency program yet.
Board Certification:
You have competed residency or a fellowship and then taken an exam that certifies you as a specialist. Here is when things get tricky. Usually, insurance companies will not pay for your procedures unless you are board certified. The ACGME grants accreditation to hospitals for residency programs. It also is the recognizing body for fellowships. The good news is that if ACGME accredits it, Medicare pays for it. The bad news is that other, non-recognized programs are left on their own. There are new fellowships and un-popular fields where the hospitals have to pay for the programs themselves. The training you could receive from one of these unaccredited programs might be phenomenal, but you won't get reimbursed for your future work from an insurance company. Some quick examples that I can think of are the clinical nutrition fellowship for primary care fields and the urgent care fellowship for family practice docs. Also, there is another certifying body called the AAPS. It only provides board certification, and not residency accreditation. It has received legal recognition in some states, but is not on the same level as ACGME.