Your best option may be to recreate the image using a vector program such as Inkscape (free, multi-platform). Inkscape supports bitmap tracing, which will reduce the workload a bit.
I've taken your tiny bitmap and ran it through the tracing and the results were not particular encouraging. It does a form of color separation, but that would require manual adjustment to get the level of detail inherent in the image.
Once converted to vector, enlarging the image causes no deterioration.
You may get suggestions that the Graphic Design SE would have been a better location for your question, but the answers are likely to be similar.