You can't stain over epoxy. Epoxy paint/concrete (epoxy=2 stage, mix the stages, chemical cure) coating is a very resilient and good choice, but is expensive and more difficult to work with, and will wear about the same as a one-step paint in an outdoor environment.
Otherwise, choose something like a high-hide masonry primer and paint it -- or choose a one-step masonry paint. Don't just use your average latex house paint.
Behr makes a good one-step masonry paint. I haven't used an epoxy, but they're most common indoors (in garages) -- Only ones that I personally have seen/used outdoors are very expensive combinations intended for traction in marine environments. My favorite paint company, Benjamin Moore, makes a primer and paint combination. The primer affixes to the concrete and then the paint adheres to the primer. I personally believe that a high grade paint and primer combination is the longest lasting solution. Your local Benjamin Moore or Sherwin Williams paint store will guide you to the best application for your location and climate.
Regarding patching, see this post: Is it possible to patch concrete stairs? -- Basically, you can re-coat the entire stair set in cement and dye that, but it will chip off.
And regarding primer or paints for concrete, see this post: Do I realliy need to use primer when painting an unfinished concrete floor?