A gradient brush is sort of an oxymoron in Photoshop terms. You wouldn't be able to change its color, so then it's not a brush; it's a stamp. I do wish that Photoshop had some kind of image pipe like the Gimp, or even something like the Symbol Sprayer from Illustrator.

You have access to the brush palette with the Clone Tool selected, but it won't do what you want. The size and shape of the clone source will remain the same, and painting a stroke will move the clone source, also. But you could jump into Illustrator and use the aforementioned Symbol Sprayer to get something close. It might take some jiggery-pokery to create a vector symbol that will mesh with a raster map, though.