I have been working with rust patinas lately, I have been using products from Sculpt Nouveau. I have written about my experiences here http://grimvisions.com/2007/04/29/horatio-gets-a-handtool/
The products actually cause rust, and oxidation to take place. The are really cool and you can achieve some really nice effects.
Here are some pictures
Yes, I painted the skull with black spray paint, then "Iron Coating B" (2 coats). As the second coat was still wet I painted on "Tan Patina". Then sprayed the whole thing with "Tiffany Green Patina", and lightly dabbed it off with a paper towel and waited for it to oxidize.