What you want is to work in terms of HSL instead of RGB. You could find a range of hue that satisfies "greenish" and pick a random hue from it. You could also pick random saturation and lightness but you'll probably want to keep your saturation near 1 and your lightness around 0.5 but you can play with them.
Below is some actionscript code to convert HSL to RGB. I haven't touched python in a while or it'd post the python version.
I find that greenish is something like 0.47*PI to 0.8*PI.
/**
@param h hue [0, 2PI]
@param s saturation [0,1]
@param l lightness [0,1]
@return object {r,g,b} {[0,1],[0,1][0,1]}
*/
public function hslToRGB(h:Number, s:Number, l:Number):Color
{
var q:Number = (l<0.5)?l*(1+s):l+s-l*s;
var p:Number = 2*l-q;
var h_k:Number = h/(Math.PI*2);
var t_r:Number = h_k+1/3;
var t_g:Number = h_k;
var t_b:Number = h_k-1/3;
if (t_r < 0) ++t_r; else if (t_r > 1) --t_r;
if (t_g < 0) ++t_g; else if (t_g > 1) --t_g;
if (t_b < 0) ++t_b; else if (t_b > 1) --t_b;
var c:Color = new Color();
if (t_r < 1/6) c.r = p+((q-p)*6*t_r);
else if (t_r < 1/2) c.r = q;
else if (t_r < 2/3) c.r = p+((q-p)*6*(2/3-t_r));
else c.r = p;
if (t_g < 1/6) c.g = p+((q-p)*6*t_g);
else if (t_g < 1/2) c.g = q;
else if (t_g < 2/3) c.g = p+((q-p)*6*(2/3-t_g));
else c.g = p;
if (t_b < 1/6) c.b = p+((q-p)*6*t_b);
else if (t_b < 1/2) c.b = q;
else if (t_b < 2/3) c.b = p+((q-p)*6*(2/3-t_b));
else c.b = p;
return c;
}