The main purpose of this work is to establish new coincidence and common fixed point theorems using contractive and Lipschitz type conditions for nonself single-valued and multivalued mappings (not necessarily continuous) on a metric space and cite their applications in approximation theory and eigenvalue problems. A general iteration scheme for a finite family of asymptotically quasi-nonexpansive mappings in Banach spaces is introduced and its convergence to a common fixed point of the family is studied. Random versions of these results are presented. A deep result concerning the existence of random fixed point of an inward multivalued random operator on a separable Banach space with characteristic of noncompact convexity less than 1 is also proved.