I know I'm a little late on this thread, seeing as how there are already viable answers, but I have an alternate solution. Instead of worrying about generating each byte individually, why not generate the number as a whole:

my $pre = '00:96:14:';
my ($minhex,$maxhex) = qw(0 2fffff);

# Randomize a number between $minhex and $maxhex, inclusive
# Accounts for a min value other than 0
my $hostiddec = int(rand(hex($maxhex) - hex($minhex) + 1)) + hex($minh
+ex);

# Convert to hex again
$hostidhex = unpack("H*",pack("i",$hostiddec));

# Format, getting rid of leading 0's and adding colons
$hostidhex =~ s/^0*(\w{2})(\w{2})(\w{2})$/$1:$2:$3/;

# Output (return here rather than print if you're in a subroutine)
print $pre . $hostidhex;
[download]

I don't know why it seems clunky to me to generate the bytes individually. For instance, I find it easier and more efficient to int(rand(16)) and convert it to binary than int(rand(2)) 4 times and concatenate it. Seems to me like your output would be more varied, but that's probably just me. Mathematically it seems like it would be the same (16 possibilities for the former, 2*2*2*2=16 possibilities for the latter), but I just feel like the former offers more variety. When you only have 2 choices, even when repeating it 4 times, I just see repetition of the final pattern being more common. I'll stop babbling now.