CP Gear Icon missing? Created new Super Admin account
'Admin' permission is set on the user level, whereas 'userGroup' permissions are set on the userGroup level. And as far as I know, 'admin' permission should trump any userGroup permissions. I'm not sure how you got locked out, unless you unchecked the 'Admin' checkbox on your user profile settings perhaps? Regardless, setting the 'admin' value to 1 in the craft_users table should be sufficient to restore privileges, without clearing out the other tables.

The only way to create other Admins is to check the 'Admin' checkbox on the user profile permissions tab. The next best thing is create a userGroup (called 'administrator' for example) with all of the permission boxes checked. Keep in mind however, that userGroup permissions need to be set explicitly, so if you create a new section, you may need to update the userGroup permissions to allow the new section.