The viewing distance of an image is somehow proportional to the size of the print.
For example you normally do not see a magazine from across the street, and you do not see a billboard very close.
That means that you can use the same photo on a magazine and on a billboard.
If you have a 10Mpx photo, guess what? You use your 10Mpx photo.
(These imagee have a mistake: Where they say dpi it should read ppi.)
You need to do some things on a vector graphics program, like texts, logos and other stuff.
You can prepare your artboard on a scale. If you need a 4x3m billboard, you can do it at 40x30cm, and at the end export a jpg file.
Here is a graph to give you an idea, based on the previous explanation:
Work on your image with Photoshop or Photowhatever, but insert the texts on a vector based program. Illustrator, Corel, InDesign, etc.