Inkscape can be found on the internet in portable format, and it allows you to convert any image to a vector image. You can do this by going Path > Trace Bitmap in the menu. But I have to admit it's not the most straightforward solution, because you have to do a series of steps to achieve the conversion.
In overall:
1) yes, Inkscape is free
2) If you download the portable version, no install is required
3) It does the job, however it's not like a solution where you "drag and drop" and the job is done.
4) It supports most of the general formats. (png, jpg, bmp, but im not sure about tiff)
There are portable packages for windows, but for linux I'm not sure.