You can do this either with R or ArcGIS independently.
With ArcGIS, first create a feature class (e.g. shape file) from your grid coordinates. Then use this grid feature class as constraining_extent parameter of "Create Random Points" tool.
The only coding you have to do is to put that tool in a loop which can be achieved via Model Builder or Arcpy.
here is a sample (100 iteration):
import arcpy
for i in range(100):
print i
arcpy.CreateRandomPoints_management("c:/data/project", "samplepoints", "c:/data/studyarea.shp", "", 500, "", "POINT", "")
For R, use genrandompnts from spatialecology website. This tool is similiar to ArcGis "Create Random Points" tool.
In addition, there is another thread similiar to your quesiton.
How to create random points outside polygons?How to create random points outside polygons?