The picture of that lock really suggests that the cylinder is removable via a screw that is accessible when the shackle is open.
Sometimes this screw fits an allen-key rather than a screwdriver, although I am sure that you would have noticed this when you were looking down into the shackle's bore. I have seen the hexagonal hole for the allen-key obscured by grease/dirt, but your lock looks very clean.
At MasterLock's website, the specifications of this lock do not list that it has a removable/rekeyable cylinder (
http://www.masterlock.com/cgi-bin/produ ... t_id=D7035).
There are some locks that I have seen where the screw under the shackle which holds the cylinder-retaining plate in place has had the head of it machined off, making it impossible to remove with juts a screwdriver/allen key.
I hope this is not the case with this lock.
Hopefully somebody that has hands-on experience with this specific lock can contribute.
...Mark