应该不是很难办

他原来公司还有认识的人没有？如果有，可以帮着跟头头联系一下，又不是做伪证，出个证明信，盖个公章应该没问题。

或者你可以打电话跟使馆联系一下，看如果出国前没工作的应该如何来办。