The "best" way would be to re-photograph it with a fine grain emulsion film (real, "PHOTOGRAPHY") and then blow that up using optics the way it used to be done.
Next would be to scan it at the highest resolution you can get. I have a scanner that will do an interpolated 1200 dots per inch (actual 600 dpi, but it doubles that and averages/blends the adjacent dots). Then, reprint it at only 600 dpi to double the size (quadruple the area).
There are dozens of photo editors that can re-sample a scanned image to change the size and keep the dots per inch the same, (the same scheme used by the scanner to get to 1200 dpi from 600 dpi). These photo editors are usually free with cameras and scanners. Microsoft Office comes with a photo editor also. I am sure there are some free ones on the web too.
Just doubling/tripling/etc. the size of an image is what creates the blocky pixelation you are trying to avoid. You need the re-sample function of the photo editors to overcome that. You might want to then do some "Sharpen" and "Blur" functions to try to hide any remaining blockyness.
BE SURE you keep previous versions each time you make major changes so when you get done and realize you have ruined the image (a common occurrence as your eye becomes jaded by the difficulty of detecting which function actually did some good and which ones actually made something worse!)
Also, realize that each time you save an image in any format other than a Bit Map (.bmp), especially a format that compresses the image (such as .jpg or jpeg) that some of the purity of the resolution is lost when you re-open the image to edit it. Of course Bit Maps make for HUGE files.