1) Write a letter of explanation RE employer's refusal to provide the required letter (include proof). Could this be an email from the company HR or something?
Yes.
2) Provide alternative documentation - this letter is one piece, be sure the person who signs includes contact information and/or a business card. What kind of alternate documentation? ?? Weren't we discussing an unofficial letter from a colleague? Other items could be a contract, paystubs, etc.
3) Provide other records, such as a contract, Record of Employment (if you are no longer there), along with the T4.What is the T4?
Sorry, T4s are for people who work in Canada, they are annual wage/remuneration statements provided by employers to employees for income tax purposes (like W2s in the USA). If you have a similar document from your country, you could use that too.