How can I add a message to an iPhone in erase mode
If you had at least iOS7 then when activating lost mode it will give you field to enter phone number you can be reached at regarding lost iPhone. When phone is online (even after restore) then message that phone is lost with number to contact be displayed.

Apple has a page on it called If your iPhone, iPad, or iPod touch is lost or stolen