He is a very small little guy! Thanks for rescuing this black beauty. I wouldn't use an aluminum
pie tin for the litter, as most cats don't like scratching on it. Your litter box shouldn't have sides higher than 2 inches and should be at least 12" x 12" --- better box is too big than too small! If it's struggle for him to get into your litter box, yes he will take the easy way and do it outside of the box. You might try some "Cat Attract" litter http://www.preciouscat.com/
that some people say is successful at getting cat to go in the box.
You're right in wanting to get him trained correctly as quickly as possible before it becomes a bad habit. Do praise him lavishly when he does use the box. Good luck!