Achieve outline effect in texture
The basic idea for generating outline effect comes from Cycles Wireframe Shader from agus at BlendSwap.

General Step:


Create a UV layer (which is used for generating "procedural" wires), then unwrap the mesh by the "Reset" method in U menu.
Create another UV layer (used for baking), which should contain the expected UV.
Create an Image Texture node and keep it disconnected to any socket. then bake Diffuse color onto the target image.






NOTE: Before baking, make sure the target UV layer is activated.

More guidelines about baking.



EDIT:

There should be more than one way to do so. Another way is to use Texture Paint mode to paint it manually: Select all Faces then hit I twice to Inset individual faces, then invert selection for masking in paint mode. It does work, but you can hardly get smooth result in this way.

A third way is using Export UV Layout. Though you've mentioned that "Export UV Layout" should not be an option here, I still recommend you to try Paul Gonet's solution again. Just plus one more tip —— use Dilate/Erode node to get proper outline width. Then you can use File Output node to output the outlined texture while rendering again. Finally you can reuse it back to the model.