I am trying to find a suitable locking design to do the the following:

APP SERVER A -->
APP SERVER B ----> CENTRAL MYSQL DB SERVER
APP SERVER C -->

(i.e. 3 app servers and 1 mysql server)

The mysql server database will have a table call jobs and each App server will have a service that pickups job from table, mark as in progress, and then update the job when done.

i.e.
SELECT * FROM Jobs WHERE Status = 'New' ORDER BY Created DESC LIMIT 5. (get the 5 most recent 'new jobs').
UPDATE each one to Status='In Progress'
Do the job
UPDATE each one to Status='Complete'

However I'll have 3 servers each running the above and my concern is they will both grab the same (or partially the same) set of records before one is able to update them as 'In progress'.

Any ideas? I'd like to avoid using LOCK Tables as well, since it doesnt seem very efficient.

I ran into something like this a while ago.

What you might want to think about doing is cronning (I assume you'll be cronning?) the jobs to run at different times. So they never even come close to overlapping. Depending on how often your going to have the app servers run.

* Edit * - Another way might to be make another interface on the server which the app servers communicate with then in turn the program/script/whatever interface gets the information from the mysql db and relays it to the app servers. That might be the best way if you ever wanted to add more than 3 servers or you don't want to mess with the timing on the cron.

* Edit * - Ok even a third way which you might want to consider. Only grabbing 1 job at a time, but looping it 5 times. So:
Server 1 gets job #1 instead of #1-5
Server 2 gets job #2 instead of #6-10
Server 3 gets job #3 instead of #11-15
Server 1 finishes job #1, see's that #1, #2, #3 are being worked on or have been finished and goes to #4
etc..

let say you make in talbe jobs.. a field "updated"
When you update.. set it to 1
Get appropriate server to check if it equals 1..
and after it finishes .. sets it to 0..
etc.

How frequently are new jobs created, and how long will each take to be processed?

If you write the query that takes ownership of jobs so that it can't take any jobs that have already been assigned, you shouldn't need to worry about two servers ending up with the same jobs:
UPDATE Jobs
SET Owner = 1
WHERE Owner IS NULL
After updating the ownership, you'd want to do a select to see which jobs you took.

You can make the column you use to indicate that a job is in progress an integer. When an app server wants to grab the job, have it increment this integer. If the result is 1, then it can begin executing the job. If it's greater than 1, it should decrement the number and try a different job.

There is a limitation to this approach. It's possible that two or more app servers may contend for the same job without any of them succeeding in grabbing it. This happens if two or more increment the value before the first one checks the result. This can result in the first job not being executed first. Whether this is a problem or not depends on what you're trying to do.

Also, it seems from your post that you may need to lock multiple rows in order to execute a job. If this is the case, you must lock rows in the same order every time or release all the rows when an app server finds a row already locked. Otherwise, you may get a deadlock.

Since you're using mysql, pay careful attention to which table type you use, and whether you might need a different database (like PostgreSQL) that scales better with high levels of concurrency.