Take a look at this extension called Delete My Account:
http://extensions.joomla.org/extensions/clients-a-communities/user-management/26011
It allows users to delete their own account via the frontend. There is also a feature where it notifies all admins if a user has deleted their account. Looks like a promising extension and exactly what you need. Compatible with Joomla 2.5 and 3.x
Update:
I have just tested this plugin on my localhost and it works perfectly fine.
- Install the plugin
- Enable it and in the options, set Action to be taken to delete
- You then need to place a link with with a specific class. You can place this link literally anywhere you want. I decided to put it in an article, simply to test. So add the following somewhere on your site:
<a href="#" class="f90-delete-my-account">Delete my account</a> - When you click on this link in the frontend, it should load a modal box asking you to confirm that you want to delete your account.