Basically when you select Insert -> Web Part you get this menu:
Is it possible to determine what is available here based on a users role?
I just came across this post from Waldek that might be useful for you.
Go to the Web Part Gallery in your Site Collection. Select the Web Part. In the ribbon under the Documents Tab choose Document Permissions. There you can manage permissions for the web part.
I think it can be done. I've worked with the Web Part Adder class myself, thanks to Wictor and Anders. The class runs within the context of the user, so you can use that to possibly strip out specific web parts you don't want a user to see, depending on security role.
Keeping track of what specific web parts a user can and cannot see is up to you, as you have full control of the class which gets the web parts for the gallery.