I have been asked for the following documents:

1. 履歴書
2. 職務経歴書

I think I could figure out (1) by myself but I'm sure someone here that has already gone through this agony could offer some advice and/or guidance. And, what is (2) about?

http://www.rirekisyodo.com/
I use this site for tips when working on resumes. The 履歴書 will likely be a set form (and also includes your 職務経歴) but the 職務経歴書 itself is likely free form. See also 職務経歴書の書き方
and
履歴書の様式について