How to select and delete all Output cells?

Without adressing the hotkey issue (you could add a menu entry, or simply put an appropriate Button in your notebook), here is one variety that uses NotebookDelete and can be modified to include different CellStyles as well. The first argument nb defines which notebook to work on, the second argument styles defines the styles of to-be-deleted cells:

CleanNotebook[nb_: SelectedNotebook[],styles_: {"Output"}] := 
   (NotebookFind[nb, #, All, CellStyle];
    NotebookDelete[nb];) & /@ styles

Together with NotebookOpen, NotebookSave and NotebookClose and related functions you should be able to work on arbitrary notebooks programmatically.

Example:

docpath = 
  ToFileName[{$InstallationDirectory, "Documentation", "English", 
    "System"}, "ExampleData"];

nb = NotebookOpen[ToFileName[docpath, "document.nb"]]

CleanNotebook[nb]

Take care what other styles you choose, they´ll be gone for good...

Edit: You may also use the Option Visbible->False to supress the opening of a window for this notebook. This seems useful for batch processing (especially if Dynamic stuff is involved, because this will probably not trigger if invisible), but takes additional care to save and close programmatically because invisble windows do not show up in the menu bar.

Example:

doc = ToFileName[{$InstallationDirectory, "Documentation", "English", 
    "System", "ExampleData"}, "document.nb"];

bak = ToFileName[$TemporaryDirectory, "document_clean.nb"];

nb = NotebookOpen[doc, Visible -> False];
CleanNotebook[nb];
NotebookSave[nb, bak]
NotebookClose[nb]

NotebookOpen[doc];    
NotebookOpen[bak, Visible -> True];

There is still an issue with the Visible option being saved in the backup notebook and hiding when reopened (thus re-setting Visible->True).

This is how you do it through menus, As correctly noted in the comment this is equivalent to the shortcut ALT+C >> L >> ENTER.

Update December 6th: There is an updated version (plus a bug fix for M9) working on Windows, MacOSX and Linux available and installable by

  Import["http://www.mertig.com/mykeys.m"]

On Windows (Mac does not work yet): Execute the following code in a notebook and restart Mathematica.

Then hitting F4 will delete all Output, Print and Message cells in the selected notebook, while pressing F8 will do so in all open notebooks which are not Wolfram Documentation notebooks. This was more difficult to program than it should be ...

$OverWriteUserBaseDirectoryKeyEventTranslations = True;
    mymenuitems="
       (* Delete all Output, Message and Print cells in the selected notebook *)
                 Item[KeyEvent[\"F4\"(*, Modifiers -> {\"Control\",\"Shift\"}*)], 
                 KernelExecute[
                   Module[{nb = SelectedNotebook[]},
                    Scan[Function[c, If[NotebookFind[nb, c, All, CellStyle, AutoScroll -> False] =!= $Failed,
                                    NotebookDelete[nb, AutoScroll -> False]]  
                             ],
                     {\"Message\", \"Output\", \"Print\"}
                    ];
                 SelectionMove[nb,After,Notebook];
              ]
            ], MenuEvaluator -> Automatic ],\n
  (* Delete all Output, Message and Print cells in all open notebooks *)
             Item[KeyEvent[\"F8\"], 
             KernelExecute[
               Module[{nbs = Notebooks[]},
                Quiet[nbs = Select[nbs,  Function[z, Not[StringMatchQ[ Replace[ NotebookFileName[z], $Failed :> \"\"],
                                                                           \"*Wolfram*Documentation*\"]]]]];
                    Do[
                    Scan[Function[c, If[NotebookFind[nb, c, All, CellStyle, AutoScroll -> False] =!= $Failed,
                                    NotebookDelete[nb, AutoScroll -> False]]  
                             ],
                     {\"Message\", \"Output\", \"Print\"}
                    ];
                 SelectionMove[nb,After,Notebook],
                {nb,nbs}]
              ]
            ], MenuEvaluator -> Automatic ],";
Quiet@CreateDirectory@FileNameJoin[{$UserBaseDirectory,"SystemFiles","FrontEnd","TextResources",$OperatingSystem}];
mykeyeventtrans=FileNameJoin[{$UserBaseDirectory,"SystemFiles","FrontEnd","TextResources",$OperatingSystem,"KeyEventTranslations.tr"}];
If[$OverWriteUserBaseDirectoryKeyEventTranslations===True,
    If[FileExistsQ[mykeyeventtrans],DeleteFile@mykeyeventtrans];
    CopyFile[FileNameJoin[{$InstallationDirectory,"SystemFiles","FrontEnd","TextResources",$OperatingSystem,"KeyEventTranslations.tr"}],mykeyeventtrans]
];
keytext=Import[mykeyeventtrans,"Text"];
mykeytext=StringReplace[keytext,"EventTranslations[{":>StringJoin["EventTranslations[{\n",mymenuitems,"\n"]];
Export[mykeyeventtrans,mykeytext,"Text"];