You can (re)define keyboard shortcuts from the "Shortcuts" tab of "Keyboard"
in the "System Settings".
As far as I know, Trisquel's default interface does not allow to search
applications. But you can install another desktop environment. GNOME Shell,
for example, has the feature you want. To get it, install "gnome-shell" and
"gnome-session", log out the graphical session, and log in back after
choosing the GNOME session (icon at the right of your user name). See
http://wiki.gnome.org/GnomeShell/CheatSheet for useful shortcuts and
http://extensions.gnome.org for extensions.
You can install BleachBit on Trisquel. It is in its repository.
what extension does not work with IceCat? Does it work with Abrowser? If so,
another extension (installed by default in IceCat) may badly interact with
the one you want.