I use this to make MACs for my VMs and virtual NICs. The 00:16:3E prefix means it's Xen virtualization, so change this part as needed.

#!/usr/bin/python

# macgen.py script to generate a MAC address for guests on Xen

import random

def randomMAC():
	mac = [ 0x00, 0x16, 0x3e,
		random.randint(0x00, 0x7f),
		random.randint(0x00, 0xff),
		random.randint(0x00, 0xff) ]
	return ':'.join(map(lambda x: "%02x" % x, mac))

print (randomMAC())

Use

$ macgen.py 
00:16:3e:17:ed:b1