Yes a standard medical regulator is sufficient for your purposes. You will want one with the lowest possible measurements you can find, and possibly even a secondary rotameter to dial it back to your desired flow rates. Most likely below 0.5 liters per minute. There are two main types of valves on O2 cylinders, one medical (square, no threads) and one industrial (threads).
The fire department will likely not be able to refill your oxygen cylinder as they use compressed breathing air, not oxygen. I know because I used to fill cylinders at a fire department. Most contract out their bottle filling unless they are fairly large. The compressors take breathing air and compress it, where oxygen would be typically filled from a LOX tank (liquid) produced by someone else. Fire departments may have confined space "re-breathers" that use small (5# or less) cylinders of pure oxygen, but these are a threaded fitting, not the medical style. The department will likely be able to point you to a company that can fill (and test) the cylinder though. If it is a big department, then it could be combined with the emergency medical services and may be able to fill or swap your cylinder.
Last point, you really don't need oxygen unless brewing high gravity (above about 16*P). Regular air will work fine and reduces the chance of over-oxygenating. Oxygen is toxic to yeast at high levels. You can use a diaphragm aquarium or horticulture pump and a sanitary filter disc to aerate easily and cheaply. All that said, I use O2 and just measure it appropriately.