AttributeError: '_RestrictContext' object has no attribute 'space_data'
The solution was as easy as replacing 

script_path = bpy.context.space_data.text.filepath
icons_dir = os.path.join(os.path.dirname(script_path), "icons")


by 

icons_dir = os.path.join(os.path.dirname(__file__), "icons")


Problem solved.

Full example script:

import bpy
import os
import bpy.utils.previews

bl_info = {
    "name": "Icon problem as addon",
    "author": "X",
    "version": (1, 0, 0),
    "blender": (2, 76, 0),
    "location": "",
    "description": "Test",
    "warning": "",
    "wiki_url": "",
    "tracker_url": "",
    "category": "User Interface"}

# ¸¸♫·¯·♪¸¸♩·¯·♬¸¸¸¸♫·¯·♪¸¸♩·¯·♬¸¸¸¸♫·¯·♪¸¸♩·¯·♬¸¸¸¸♫·¯·♪¸¸♩·¯·♬¸¸¸¸♫·¯·♪¸¸♩·¯·♬¸¸¸¸♫·¯·♪¸¸♩·¯·♬¸¸

def addon_button(self, context):
    layout = self.layout

    global custom_icons 

    row = layout.row(align=True)
    row.operator("object.mode_set", text="", icon_value = custom_icons["icon_not_available"].icon_id).mode = 'OBJECT'  

# global variable to store icons in
custom_icons = None

def register():

    bpy.types.VIEW3D_HT_header.prepend(addon_button) # Here we add our button in front of the View 3D header. 

    # Our external Icons
    global custom_icons
    custom_icons = bpy.utils.previews.new()
    # Use this for an addon.
    icons_dir = os.path.join(os.path.dirname(__file__), "icons")

    # Use this inside a script
    #script_path = bpy.context.space_data.text.filepath
    #icons_dir = os.path.join(os.path.dirname(script_path), "icons")

    custom_icons.load("icon_not_available", os.path.join(icons_dir, "NOT_AVAILABLE.png"), 'IMAGE')

def unregister():
    global custom_icons
    bpy.utils.previews.remove(custom_icons)

# This allows you to run the script directly from blenders text editor
# to test the addon without having to install it.

if __name__ == "__main__":
    register()