Where to store properties on console
After two days of searching/tinkering I've found the solution.

First of all, this solution does not save the properties with the .blend file. It will reset all the properties every time you reopen blender. 



Step 1: Create the PropertyGroup

So the first step is to create a PropertyGroup holding all the properties you want to store on the console:

class ConsoleProps(bpy.types.PropertyGroup):
    str_prop = bpy.props.StringProperty()
    int_prop = bpy.props.IntegerProperty()


Step 2: Create a Collection Property on the screen.

Because consoles are indeed a part of the screen and not the scene, put a CollectionProperty on Screen.

bpy.types.Screen.consoles = bpy.props.CollectionProperty(type=ConsoleProps)


Step 3: Identify the individual consoles.

At this point you can add a console to the collection but you need some way to identify it. Because I was using it in conjunction with blenders builtin module console_python (sorry, I couldn't find any documentation),
I used the hash of the window region (bpy.context.area.regions[1] is a quick way to get it, not sure if this will ever brake). So at this point you could add a console to the collection like this:

console_id = hash(bpy.context.area.regions[1])
console = bpy.context.screen.consoles.add()
console.name = str(console_id) # Because the name has to be a string.


If you aren't using this along with the console_python module then you could simply use hash(bpy.context.area)

Note that because this is using the hash function it will always return a different value when you reopen blender. This means that any variables you change on the console will get reset to whatever their default values are.
If anyone knows of a way to make this return the same value every time, I'd love to hear about it.

Step 4: UI/Tracking Consoles

At this point all the infrastructure is in place, it's just a matter of actually adding the consoles to the collection. The best way I've found to do this is in the UI (somewhat of a hack). Just setup a basic UI on the console (probably on the header). In the draw function, check to see if the current console is in the collection, if not add it. It may look something like this:

class ConsoleHeader(bpy.types.Header):
    bl_space_type = 'CONSOLE'

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

        # This could be hash(context.area)
        console_id = str(hash(context.area.regions[1]))

        # Make sure this console is in the consoles collection.
        if console_id not in context.screen.consoles:
            console = context.screen.consoles.add()
            console.name = console_id

        # Display the console props, just because.
        layout.prop(context.screen.consoles[console_id], 'str_prop')
        layout.prop(context.screen.consoles[console_id], 'int_prop')


Something interesting about this approach is that you don't even need display anything in the UI. All you need is the draw function which get's called on every console in the layout. So if you don't want a UI, just don't display anything in draw.

Step 5: Cleanup

At this point everything will work (except that you need to register the classes of course) but if you reopen blender multiple times, screen.consoles will contain a lot of consoles that no longer exist. There is an easy way to fix this using bpy.app.handlers:

import bpy
from bpy.app.handlers import persistent

@persistent
def flush_consoles(dummy):
    for screen in bpy.data.screens:
        screen.consoles.clear()
bpy.app.handlers.load_post.append(ftlush_consoles)


This will clear the datablocks every time you open a new file. That way you won't end up with a huge collection of consoles that no longer exist.

Hope this helps anyone else trying to do the same thing. It took me quite a bit of experimenting to get it right. If anyone has any suggestions, please let me know in the comments.