In my last position as DBA, I used PasswordSafe to generate / store complex passwords. In the "Notes" section I would also include who requested it, when, and what server / database / application it was for. Access to the safe was limited to about 5 folks total (myself and a few other trusted folks / system admins).

The username / password was then emailed to the requestor in a PGP encrypted email.