Not the most elegant solution but here is what I did.
1) My raster map in question was actually a MASK where all the cells where all the cells were=1. So I just set my region to the are I wanted my cells outputted and ran
r.mapcalc myMaskRand = rand(1,1000)
2) Then I just converted that map to vector using
r.to.vect input=myMaskRand output=myMaskRandV feature=area
3) Then a bit of v.clean and I was good to go.
The only problem is that there were a couple of times that the resulting raster map had duplicate cell values and those cells were lumped. I suppose the best way of ensuring this not happening would be to run
r.mapcalc myMaskRand = rand(1,1000)*rand(7,77)
or something equivalent.