Hey Jonny, both cameras are excellent choices and I've owned several copies of each.
Finding batteries for the OM-1 is not really a big deal. You can buy 1.35 hearing aide batteries that fit it at any grocery store for very little money or get the proper replacement Wein Cell batteries at any decent camera shop or online. The mercury battery issue is really blown out of proportion. I only mention this because, while it's awesome to guess exposure, if you have a working meter, it can help you confirm your guesses.
The OM-1 is a more professional camera than the K1000 as it has an interchangeable viewscreen (which makes cleaning easier and allows for use of custom focusing screens,) mirror lock-up and DoF preview. The K1000 is probably more robust though, providing you pick up a metal Japanese one. The size of the OM-1 makes the internal parts smaller and this reduces reliability, which is partly why you never see other compact professional 35mm SLR's. That being said, both cameras will withstand heavy use and abuse when serviced properly.
For fast, street photography, I prefer the OM-1, and particularly the OM-1n with its more ergonomic advance lever. The smallness of it is very unintimidating and if you get a black body (in which the K1000 never was offered) you have a very stealthy little camera. The fact that you can also remove the hot shoe adds to this. The shutter speed dial around the lens is very quick to use in my opinion and I prefer this lay out to the conventional dial on top of the camera. It allows you to hold, fire and advance with on hand and make all the settings with the other without shifting the weight of the camera and lens from hand to hand. The OM-1 copied the Nikkormat FT series in that respect.
The Nikkormat is even tougher than both the K1000 and OM-1 but is a bit larger. I find it's shutter dial even faster to use and IF you were going to use a meter the Nikkormat FT cameras have a read-out both inside the viewfinder AND on top of the camera, which is REALLY useful for candid shots. A black Nikkormat FT2 makes a very nice street shooter in my opinion. Deadly accurate and reliable, can be used as a weapon if necessary! More ergonomic and reasonably quiet and small (as long as you don't use longer lenses, the OM lenses are pretty tiny.)
One edge the OM-1 has over all these cameras though, is the quiet cloth shutter which is modeled after the most famous street cameras, Leica. The OM-1's shutter is probably the quiest of any mechanical SLR.
Lens wise, you can get the same types of lenses for around the same prices with all these cameras. The OM lenses are a little price by small and high quality. I would recommend the 28mm 2.8, 50mm 1.4 or 1.8, 85mm f2, 100mm 2.8 and 135mm 2.8. You can get all these lengths in Pentax too if you wanted. And you can get these and many more in Nikon.
Olympus Zuiko lenses have a lot of contrast to them and render textures well and have very pleasing out of focus areas. Here are a few shots with my 50mm 1.8
http://www.flickr.com/photos/johnnymartyr/3859302777/
http://www.flickr.com/photos/johnnymartyr/3875345522/
http://www.flickr.com/photos/johnnymartyr/4151118677/
http://www.flickr.com/photos/johnnymartyr/4518967714/
Buy a reliable camera from KEH.com, PennCamera.com or CameraRepair.com
Metal & Manual! Film Forever!
EDIT: The Pentax MX is a good alternative to the OM-1 but the most of its advantage is in its metering read-out which is fairly unimportant to the Jonny. They also sell for more than the OM-1 and are more prone to failure in my experience. I do like the shutter release lock and the Pentax 40mm pancake lens is a thing of beauty. The MX is also SLIGHTLY taller and thicker than the OM-1. I would only suggest an MX over an OM-1 if you are already in a Pentax lens system or want a full sized camera like the K1000 or LX for less stealthy shooting also.