> Is there currently some package available that allows managing custom
> key bindings on a per-keymap-basis through the `customize` interface?

Not really, AFAIK.  But there might be some related discussion on
emacs-devel or the Emacs bug list.

> I got a bit annoyed recently by losing track of all the custom
> keybindings I have made, so I wrote a function, that automatically
> adds an entry in a menu in global-map for every custom keybinding.
> Now I am intending to extend this to utilizing the custom interface for
> creating keybindings on a per-mode basis.
> 
> While relatively easy to do, I'd prefer a commonly used solution, if
> there is any.
> 
> PS: I'm still not sure whether such questions should go to emacs-help or
> emacs-devel.

Either is probably OK in this case.  emacs-devel might be a bit better,
since this would be a new development/feature.  But with help-gnu-emacs
you might get more info about existing 3rd-party features.  You can also
file Emacs enhancement requests, using `M-x report-emacs-bug'.


FWIW, I sometimes provide user options that have key-binding values.
Not a complete solution, but it can make things easier.

For example, option `icicle-top-level-key-bindings' is an alist whose
entries are of defcustom :type `icicle-key-definition', which means that
they have the form (KEY COMMAND CONDITION), where KEY is either a key
sequence (string or vector) to bind COMMAND to or a command to remap
to COMMAND.  COMMAND is bound according to the value of KEY, unless the
result of evaluating CONDITION is nil.

In Customize, to specify a key sequence, you choose `Key' in the `Value
Menu', then enter a key description such as that returned by `C-h k'.
For convenience, you can also insert a key in the key description by
hitting `C-q' then the key. For example, to enter the key description
`C-c M-k' you can use `C-q C-c C-q M-k'.

Attached is what key bindings look like in Customize.

In Lisp (e.g., to define the default value for a key-binding option),
an unconditional key binding looks like this:
  ("\C-c="  icicle-imenu  t)

A conditional key binding looks like this:
  ([f10]  lacarte-execute-menu-command
   (fboundp 'lacarte-execute-menu-command))

A conditional binding that remaps another command looks like this:
  (bmkp-tag-a-file  icicle-tag-a-file  (fboundp 'bmkp-tag-a-file))

KEY can also be expressed using `kbd', of course:
  `(,(kbd "C-c =")  icicle-imenu  t)
or
  (list (kbd "C-c =") 'icicle-imenu  t)


This is the code that defines custom type `icicle-key-definition':

(define-widget 'icicle-key-definition 'lazy
  "Key definition type for Icicle mode keys.
A list of three components: KEY, COMMAND, CONDITION, that represents
an `icicle-mode-map' binding of COMMAND according to KEY, if CONDITION
evaluates to non-nil.

KEY is either a key sequence (string or vector) or a command.
COMMAND is a command.
CONDITION is a sexp.

If KEY is a command, then the binding represented is its remapping to
COMMAND."
  :indent 1 :offset 0 :tag ""
  :type
  '(list
    (choice
     (key-sequence :tag "Key" :value [ignore])
     ;; Use `symbolp' instead of `commandp',
     ;; in case the library defining the command is not loaded.
     (restricted-sexp :tag "Command to remap"
                      :match-alternatives (symbolp) :value ignore))
     ;; Use `symbolp' instead of `commandp'...
    (restricted-sexp :tag "Command"
                     :match-alternatives (symbolp) :value ignore)
    (sexp :tag "Condition")))

The code is here:
http://www.emacswiki.org/emacs-en/download/icicles-opt.el

HTH.