Best way in your situation is using some vector format (and editor)- ps/eps, svg, cdr, etc.
To be honest I have no idea if you can find free editor for vector format.
Vector image can be resized without limits. Bitmap image (jpg/png/bmp, etc.) can not.