Is it possible to get rigid body objects to move randomly in space?
This is possible. The solution contains multiple steps though (long answer).

Requirements:


random starting location and rotation
rigid bodies
no gravity
random initial velocity


In my example this resembles and asteroid field. 

Setting up objects

Create a large domain. Add a particle system to it, emit randomly from volume. Check the Rotation option and set them to random values. In the Render section use a dupli object. I randomized the scale as well for more variety.

Convert the particle modifier, then hide or remove it. The objects have been created, each with their own location, rotation, scale. Apply the scale if you wish. Ctrl+A

Create the rigid body world in the Scene properties panel. I deleted the dupli object. Select the large domain object and make it a passive rigid body with mesh boundaries. Hide it temporarily.

Select all the particle duplicates, with one as the active object. Make it an active rigid body. In my case the objects are cubes. 

Copy the settings to all selected.
This will take some time. Use few objects or be patient. After the operation all objects are rigid bodies confined to the walls of the domain object. Running the simulation with Alt+A will result in the objects tumbling onto the domain floor.Solve this, by disabling Gravity in the Scene Properties Panel.The object will now (mostly) stay as they are. They're rigid bodies which will collide physically.Unfortunately, we can not give rigid bodies a starting velocity.

Setting up an initial velocity

Rigid bodies don't have a starting velocity. But since their  can be keyframed and because rigid bodies calculate their movement on previous frames, we can achieve this with keyframes.

In this example, the cube has two location keyframes on frame 1 and 3. Its animated rigid body property is keyed to ON on frame 2 and to OFF on frame 3. Hence the speed of frame 2 is the input for frame 3 and following.

To animate all particle object over the span of two frames, I will use a python script.

The script will do the following:


get all selected objects (our particles)
get the start frame
for each object:



  
  key the first frame of the scene (location and rotation)
  translate and rotate the object randomly
  key the location and rotation to the third frame of the scene
  key the animated property to ON on frame 2
  key the animated property to OFF on frame 3
  


I will use the following modules.

import bpy
from random import random
from random import uniform
from math import pow
from math import pi


We will need a function to generate a random vector. Let's setup a threedimensional array with random values, the normalize it and multiply it with a given length (pLen).

def genRandVec(pLen):
    #setup random translation vector
    t = [random() - 0.5 for x in range(3)]
    # normalize the translation vector
    t_len = pow(pow(t[0], 2) + pow(t[1], 2) + pow(t[2], 2), 0.5)
    t = [x / t_len for x in t]
    # multiply it with the length
    t = [x * pLen for x in t]
    return t


Next up is a function which will move and rotate an object with a certain randomization. We will get the parameters:

obj          the input object
t_amount     the maximum amount of translation
t_var        the amount of variance in the translation [0 ... 1]
r_amount     the maximum amount of rotation
r_var        the amount of variance in the rotation[0 ... 1]


A random value of the variance is input into the genRandVec function. Then location and rotation_euler of the object are altered.

def randLocRot(obj, t_amount, t_var, r_amount, r_var):
    t_rand = uniform(1-t_var, 1)
    t = genRandVec(t_amount * t_rand)
    obj.location = (t[0] + obj.location.x, t[1] + obj.location.y, t[2] + obj.location.z)

    r_rand = uniform(1-r_var, 1)
    r = genRandVec(r_amount * r_rand)
    # because radians are confusing
    r = [x*pi/180 for x in r]

    obj.rotation_euler = [obj.rotation_euler[0] + r[0], obj.rotation_euler[1] + r[1], obj.rotation_euler[2] + r[2]]


With these functions we can easily assemble the required steps.

def randomTwoFrameMovement():
    # get scene variables
    sel = bpy.context.selected_objects
    scn = bpy.context.scene
    startFrame = scn.frame_start
    keyInterp = bpy.context.user_preferences.edit.keyframe_new_interpolation_type
    # set interpolation type
    bpy.context.user_preferences.edit.keyframe_new_interpolation_type ='LINEAR'
    # counter
    i = 0
    for obj in sel:
        i = i + 1
        print(str(i) + " / " + str(len(sel)))
        obj.keyframe_insert(data_path='location', frame=startFrame)
        obj.keyframe_insert(data_path='rotation_euler', frame=startFrame)
        randLocRot(obj, 0.2, 1, 2, 1)
        obj.keyframe_insert(data_path='location', frame=startFrame+2)
        obj.keyframe_insert(data_path='rotation_euler', frame=startFrame+2)

        obj.rigid_body.kinematic = True
        obj.keyframe_insert(data_path='rigid_body.kinematic', frame=startFrame+1)
        obj.rigid_body.kinematic = False
        obj.keyframe_insert(data_path='rigid_body.kinematic', frame=startFrame+2)

    # set interpolation type back
    bpy.context.user_preferences.edit.keyframe_new_interpolation_type = keyInterp


Select all particle object and call randomTwoFrameMovement(). Then, simulate the Rigid Body World.

The Calculate Mass tool is very useful. Setting the rigid body dynamics to 0 Damping results in a more space-like feeling.

 Higher Resolution