Can I use Professor Elm's Training Method if there are zero cards left in my deck?
No, you cannot search through your deck if there's nothing there to search. If there are cards in the deck you can fail to find a Pokemon because you don't know what may be in a deck, but since you do know whether there are ANY cards or not you cannot search through an empty deck.
Source: PUI Rules Team (2011-09-22)