Solution using udev
Since HAL is deprecated and udev is now used, this approach is preferred over my other answer (although I think that the solution using HAL is simpler).
However for many function keys you can simply use System Settings > Keyboard > Shortcuts to bind a script, try this first! It saves you a lot of trouble.
For for instance the brightness keys this doesn't work (I don't have a clue why not), so if you want to know how to change the behavior of for example the brightness keys, read on.
NOTE: If you are running a Samsung notebook you can fix all (depending on model) function keys by installing the samsung-tools package from http://www.voria.org/forum/
This howto assumes you know how to use a terminal, and uses the vim editor. If you don't know vim please replace it in the commands by either gedit or nano.
Determining your keyboard 
/lib/udev/findkeyboards
should print the keyboards that are connected to the computer, in my case
USB keyboard: input/event9
USB keyboard: input/event7
AT keyboard: input/event4
Now there are two options:
- USB keyboards:
 If you want to remap your USB keyboard, inspect them by running
 - udevadm info --export-db | awk '/event9/' RS="" | grep -P 'ID_(VENDOR|MODEL)(?!_ENC)'
 - where you have to replace the 9 in the awk statement by the correct number. The output should be similar to - E: ID_MODEL=USB_Receiver
E: ID_MODEL_ID=c52b
E: ID_VENDOR=Logitech
E: ID_VENDOR_ID=046d
 - which correctly indicates that my keyboard is handled via my Logitech USB Receiver (input/event7 turned out to be my Logitech G9 mouse which has some programmable buttons). 
- Laptop Keyboard :
 If you want to remap your laptop keyboard, you should remember the number for the- AT keyboardwhich is 4 in my case. Also get the dmi information  for your laptop:
 - cat /sys/class/dmi/id/sys_vendor
 - which is in my case - SAMSUNG ELECTRONICS CO., LTD.
 - and - cat /sys/class/dmi/id/product_name
 - which is in my case - 305U1A
 
Determine your current mapping of your function keys
Now we can determine our current keymapping by listening to the keyboard (insert correct number)
sudo /lib/udev/keymap -i input/event4
you can exit this command by using Esc on the keyboard, or Ctrl+c on another keyboard.
If your screen starts scrolling down very hard, press Esc and Ctrl+c a few times and try again with 
sudo /lib/udev/keymap -i input/event4 2> /dev/null
or, if you still have the scrolling issue
sudo /lib/udev/keymap -i input/event4 > ~/keymap.log
In the last case you will still have the scrolling but if you press the functions keys they should go into ~/keymap.log where you can read them later.
Now we can check the current mapping of your Function keys by pressing them, which should give you a list like (this is my Fn+F1 through Fn+F12):
scan code: 0xCE   key code: kpplusminus
scan code: 0x89   key code: brightnessdown
scan code: 0x88   key code: brightnessup
scan code: 0x82   key code: switchvideomode
scan code: 0xF9   key code: f23
scan code: 0xA0   key code: mute
scan code: 0xAE   key code: volumedown
scan code: 0xB0   key code: volumeup
scan code: 0x43   key code: f9
scan code: 0x44   key code: f10
scan code: 0xB3   key code: prog3
scan code: 0x86   key code: wlan
Now write down the scan codes for which you want the behavior to change.
Changing the key codes for the scan codes 
If you see the key code clearly doesn't cover what you expect the key to do you can have a look in /usr/include/linux/input.h under Keys and buttons to see if there is a key code that better matches  what you actually want to happen. The key codes there are in the format KEY_KEYCODE and you have have to write down the part after KEY_ in lowercase. Sometimes changing this is enough to solve the problem.
The brightness keys however often have the right keycode associated with them, and this is what doesn't allow them to be remapped. So we need to change them to other keycodes. We will use prog1 and prog2 for this example because these aren't in use on my computer, however you can also use f13 through f24, or f20 through f24 if you have an Apple keyboard which has F1 through F19 keys.
- Create a custom keymap:
 Create a keymap file in the directory- /lib/udev/keymapswith a suitable name, have a look at the output of- ls /lib/udev/keymapsto see for suitable names. I am going with- custom-brightnessfor the purpose of this question.
 - sudo vim /lib/udev/keymaps/custom-brightness
 - and enter the scan codes of the keys you want to change followed by the scancodes you want them to have. My - custom-brightnesslooks like this:
 - # /lib/udev/keymaps/custom-brightness
0x89 prog1
0x88 prog2
 
- Create a custom key release file. Only if you are changin your laptop keyboard:
 Sometimes the key release event is not properly send, causing the computer to hang. To avoid this we will also write a custom key release file
 - sudo vim /lib/udev/keymaps/force-release/custom-brightness
 - this file should contain the same scan codes, mine looks like - # /lib/udev/keymaps/force-release/custom-brightness
0x89
0x88
 
Make sure that the new mappings are loaded in the rules files
Now we need to make sure that your mappings are loaded. We can do this by editing /lib/udev/rules.d/95-keymap.rules, so it is smart to make a backup
Again we have two options:
- USB keyboards:
 Since you have a USB keyboard you should add your entry under- LABEL="keyboard_usbcheck"and it should be past the other entries of your keyboard manufacturer. This is because my keyboard with
 - E: ID_MODEL=USB_Receiver
E: ID_MODEL_ID=c52b
E: ID_VENDOR=Logitech
E: ID_VENDOR_ID=046d
 - is already matched by one of the rules, and otherwise it gets overwritten.
 Add the following rule, where you should change the- ID_VENDOR_IDand- ID_MODEL_IDand the name of your keymap appropiately
 - ENV{ID_VENDOR_ID}=="046d", ENV{ID_MODEL_ID}=="c52b", RUN+="keymap $name custom-brightness"
 
- Laptop keyboard:
 If- /lib/udev/findkeyboardsreported your laptop keyboard as- AT keyboardyour rule should go under- LABEL="keyboard_vendorcheck", otherwise put it under- LABEL="keyboard_modulecheck". Again put it under the other entries for your laptop manufactorer. Add the following rule (- SAMSUNG ELECTRONICS CO., LTD.is bit long so I used a wildcard`)
 - ENV{DMI_VENDOR}=="SAMSUNG*", ATTR{[dmi/id]product_name}=="305U1A", RUN+="keymap $name custom_brightness"
 - Now also add a rule to - /lib/udev/rules.d/95-keyboard-force-release.rulesafter backing it up
 - sudo cp /lib/udev/rules.d/95-keyboard-force-release.rules /lib/udev/rules.d/95-keyboard-force-release.rules.bak
sudo vim /lib/udev/rules.d/95-keyboard-force-release.rules
 - Again under the other entries of your manufacturer add - ENV{DMI_VENDOR}=="SAMSUNG*", ATTR{[dmi/id]product_name}=="305U1A", RUN+="keyboard-force-release.sh $devpath custom_test"
 
Make sure udev loads the new rules
To load the new rules run
sudo adevadm trigger
NOTE: udevadm control --reload-rules (still in instructions on many websites) does not work.
Now check if the rules were applied successfully by
sudo /lib/udev/keymap -i input/event4
which should now report for the brightness keys
scan code: 0x89   key code: prog1
scan code: 0x88   key code: prog2
Remap the keys in System Settings
If the last step reported the correct key codes, either the keys start automatically working (in case they first had the wrong key codes). 
For the brightness you still have to bind the keys to a scrip which is now possible using System Settings > Keyboard > Shortcuts.
Enjoy
Notes:
- If your keys had the wrong key code and were fixed by this approach, please follow the instructions in - /usr/share/doc/udev/README.keymap.txt.gz(you can open this without extracting using- zless) and send your results the email adres mentioned there, then the changes can be included in the next release. Many users will benefit!
 
- Many thanks to this helpful post by Vaidas Jablonskis.