Battle Moveset

A Good Moveset for Regirock would have to be this:

Attacks:

Hidden Power [Rock]/Rock Slide
Earthquake
Focus Punch/Curse
Explosion/Curse

Items Attached:

Leftovers OR
Choice Band

Preferred Nature:

Adamant OR Jolly

Strategy Using Regirock

Your basic Choice Bander set here. Your best bet for getting into play with this would be to switch in on something that fears the likes of Regirock (such as Blissey and things weak to Rock attacks) or switching into Choice Banders yourself while they use a move such as Return or Aerial Ace/Hidden Power [Flying] (make sure not to switch into Earthquakes though, since they will dent the hell out of Regirock). Once you've bought yourself a free turn your best bet would be to lead with Focus Punch, since 9 times out of 10 a Skarmory or Suicune will switch in. Just keep Focus Punching if it's Skarmory who comes in, since even if it does attack, Drill Pecks mean nothing to something like Regirock. Chances are you'll force it to PHaze you away or force it to switch. If it's Suicune you'll have to leave it up to your instincts on how to react.

A variation to this would be to use Curse as a boost to make up for lack of Choice Band. This is a nicer solution for those not-so-good (a.k.a terrible) at prediction. The payoff for this is nowhere near the same as using Choice Band though (in my opinion), since unlike the Choice Band set, you don't get to make a major hit on Suicune as it comes into play and in the end, you'll probably find yourself using Explosion.

Regirock got shoved with a "meh" trait, but occasionally you'll see some upsides to Clear Body, namely the ability to block Intimidates.

EV Corner:

EVs: 252 Atk / 48 Spd / 210 SDef Adamant Nature (+Atk, -SAtk)

The Speed EVs are for outrunning Blissey as well as Pokémon designed to outrun Blissey (there are quite a few). Max Attack, Rest in Special Defence for taking any Surfs you are forced to absorb. Regirock's Defence is fine as it is and boosting it any further would be overkill.

EVs: 252 Atk / 168 Spd / 90 SDef Adamant Nature (+Atk, -SAtk)

The extra Speed EVs allow it to outrun Skarmory (and Weezing) and Pokémon designed to outrun Skarmory (and Weezing). Once more, it retains Max Attack with whatever is leftover to help absorb he Surfs better.

EVs: 252 Atk / 216 Spd / 42 SDef Jolly Nature (+Spd, -SAtk)

Believe it or not, Regirock can outrun Suicune as well as all the little critters who like to outrun Suicune. It takes a huge pump of Speed EVs but Regirock can do it.

[On any of these EV distributions, more EVs could be thrown into Speed. A lot of Pokémon are trained with excess Speed EVs to outrun Pokémon trying to outrun them. Basically, you need to tag along in that game to outrun them. Anywhere between 4-28 excess Speed EVs are acceptable in any of these distributions.]

Other Optional Sets: Regirock@Leftovers
Curse
Rock Slide/Hidden Power [Rock]
Earthquake
Rest

Wannabe Snorlax basically. The weakness to Water attacks is pretty much what stops this from being effective, as well the fact that STAB/Choice Band Earthquakes will party all over Regirock if it doesn't kick off enough Curses. A lot of Special Defence and HP EV focus is required. Whatever is left to spare may as well go into your Attack stat, since it won't make a single bit of difference to that monstrous Defence.

Regirock@Leftovers
Psych Up
Earthquake
Rock Slide/Hidden Power [Rock]
Explosion/Focus Punch/Rest

This is a bit of a novelty but it "could" work. Psyching up a Snorlax's Curses or a lot of fun. To some extent you could Psych Up Suicune's Calm Minds, although that would require nearly Max Speed to Psych up prior to being Surfed. Other possibilities include some Sword Dancers who don't have anything super effective (such as Zangoose) although most sweepers with stat boosts will pack an EQ that'll spell your demise. Rest is probably the best choice to add here, although you may need one of the support moves to hit some physical walls in place of Rest. EV focus on this set should mostly be in HP with whatever is leftover thrown into Special Defence and Attack.

Strategy Against Regirock

Earthquake and Focus Punch + STAB and/or Choice Band or Surf/Grass Attacks (Leaf Blade and Hidden Power [Grass] especially).

Regirock looks good on paper but it's hugely vulnerable to the most common things. The main thing to watch out for is Explosion, since that will catch anyone off guard and will probably OHKO everything not called: Skarmory, Aggron, Steelix, Regirock, Registeel. Well predicted Focus Punches could also cause some problems for your switch ins.

Pokémon with Rock and Ground resistances (Claydol and Flygon are the only ones I believe) will mess around with it, however they'll probably force it to use Explosion and it'll end up taking your Pokémon with it.

[Minor Note that applies to all Pokémon with a tanking move: If Regirock has Curse, make sure you KO it before it's the last Pokémon, since it can be a force to reckon with you can't Phaze it away.]

Contest Moveset

A good Contest Moveset for Regirock would have to be this for the Beauty Contest best with Modest, Mild, Rash or Quiet Nature:

Attacks:

Sunny day
Fire Punch
Thunderwave
Explosion

Items Attached:

Blue Scarf

Strategy Using Regirock

If you do the attacks in this following order you should have very few problems; 1st - Sunny day/Thunderwave, 2nd - Fire punch, 3rd - Sunny day, 4th - Fire punch, 5th - Explosion

Locations in Games

Ruby/Sapphire/Emerald Desert Ruins Colosseum Trade from R/S/E Fire Red/Leaf Green Trade from R/S/E

Animé Appearences

Regirock has had one Animé Appearence. It aswell as Regice and Registeel appear to protect the Tree from intruders Movie 8: Mew and the Wave Guiding Hero - Rukario!