I think it is a misconception that an aircraft has to be certificated in order to do instruction, but not sure.
Here's the pertinent regs in the US:
91.319 Aircraft having experimental certificates: Operating limitations.
(a) No person may operate an aircraft that has an experimental certificate—
(2) Carrying persons or property for compensation or hire.
(e) No person may operate an aircraft that is issued an experimental certificate under §21.191(i) of this chapter for compensation or hire, except a person may operate an aircraft issued an experimental certificate under §21.191(i)(1) for compensation or hire to—
(2)
Conduct flight training in an aircraft which that person provides prior to January 31, 2010.
(h) The FAA may issue deviation authority providing relief from the provisions of paragraph (a) of this section for the purpose of conducting flight training. The FAA will issue this deviation authority as a letter of deviation authority.
(1) The FAA may cancel or amend a letter of deviation authority at any time.
(2) An applicant must submit a request for deviation authority to the FAA at least 60 days before the date of intended operations. A request for deviation authority must contain a complete description of the proposed operation and justification that establishes a level of safety equivalent to that provided under the regulations for the deviation requested.
(i) The Administrator may prescribe additional limitations that the Administrator considers necessary, including limitations on the persons that may be carried in the aircraft.
I wonder where the Jan 1, 2010 date came from? It appears that training with instructor supplied experimentals now requires a deviation authority. AFaIK you can always pay for instruction in an experimental you own (or borrow if you have really good friends).