The classical ring of integer-valued polynomials Int(Z) consists of the polynomials in Q[X] that map Z into Z. We consider a generalization of integer-valued polynomials where elements of Q[X] act on sets such as rings of algebraic integers or the ring of n×n matrices with entries in Z. The collection of polynomials thus produced is a subring of Int(Z), and the principal question we consider is whether it is a Prüfer domain. This question is answered affirmatively for algebraic integers and negatively for matrices, although in the latter case Prüfer domains arise as the integral closures of the polynomial rings under consideration.