Thanks to Tom Goodwillie and Ronnie Brown for their answers. Also thanks to Theo for pointing out that I posted the problem on  math.stackexchange.com/q/135173/5363.

After some thought it became clear that the pair $(X,A)$ needs to have the homotopy extension property (HEP). A simple counterexample is the following: 

Let $X=S^{1}$ (unit circle in the complex plane), $A=S^{1}-\{(1,0)\}=Y$, and $Z=\{(-1,0)\}$. The pair $(X,A)$ does not have the HEP, for if it did we would have a retraction $r$ of $X\times I$ onto $X\times\{0\}\cup A\times I$, which is not compact. The point $Z$ is a strong deformation retract of $Y$, and the deformation retraction is given by $(e^{2\pi i t},s)\mapsto e^{\pi i +(1-s)(2\pi i t-\pi i)}$.

Now, letting $f:A\rightarrow Y$ be the identity, we can easily see that $Y\cup_{f}X$ is a circle, while $Z\cup_{\phi\circ f}X$ is a 2-point space $\{a,b\}$ with the topology $\{\emptyset,\{a,b\},\{a\}\}$. This two spaces are not homotopy equivalent since the latter is contractible.

With the extra hypothesis that the pair $(X,A)$ has the HEP I believe that we can answer the original question I posted in the affirmative.

**Proposition:** Let $X,Y,Z$ be topological spaces. Suppose that $(X,A)$ has the HEP and that we have a map $f:A\rightarrow Y$ and a homotopy equivalence $\phi:Y\rightarrow Z$. Then the adjunction spaces $Y\cup_{f}X$ and $Z\cup_{\phi\circ f}X$ are homotopy equivalent.

**Sketch of proof:** The idea is to construct a topological space $W$ having both $Y\cup_{f}X$ and $Z\cup_{\phi\circ f}X$ as strong deformation retracts. For this we begin with the mapping cylinder $M_{\phi}$ of the homotopy equivalence $\phi$, and the map $F:A\times I\rightarrow M_{\phi}$ induced by the map $i\circ(f,Id):A\times I\rightarrow Y\times I + Z$ after passing to the quotient (Here $i$ is simply the inclusion of $Y\times I$ in the disjoint union $Y\times I + Z$, and $(f,Id)$ is the map defined to be $f$ on $A$ and the identity on $I$). Then, we define $W$ to be the adjunction space $M_{\phi}\cup_{F}(X\times I)$. 

In order to show that $W$ will be the right space for the job we need to combine two things:

First, For any $u\in I$, let $R_{u}=X\times u\cup A\times I$. The HEP of $(X,A)$ guarantees that $X\times I$ strong deformation retracts onto $R_{u}$. Indeed, the HEP gives us a retraction $r^{u}$ of $X\times I$ onto $R_{u}$. Note that $r^{u}$ has two components $(r_{1}^{u},r_{2}^{u})$, which we can use to define the strong deformation retraction by 

$$H_{u}(x,t,s)=(r_{1}^{u}(x,st),(1-s)t+r_{2}^{u}(x,st)).$$

Now define 

$$(H_{u},\rho):X\times I\times I + M_{\phi}\times I\rightarrow X\times I + M_{\phi},$$

where $\rho(m,s)=m$ for all $s\in I$. Then, after passing to the quotient, this map induces a strong deformation retraction of $W$ onto $M_{\phi}\cup_{F}R_{u}$. In particular, $H_{0}$ and $H_{1}$ will induce strong deformation retractions of $W$ onto $M_{\phi}\cup_{F}R_{0}$ and $M_{\phi}\cup_{F}R_{1}$, respectively.

Second, Since $\phi$ is a homotopy equivalence, the mapping cylinder $M_{\phi}$ has its top $Y$ and bottom $Z$ as strong deformation retracts.

Now, combine the strong deformation retraction of $W$ onto $M_{\phi}\cup_{F}R_{0}$ with the strong deformation retraction of $M_{\phi}$ onto its bottom to yield a strong deformation retraction of $W$ onto $Z\cup_{\phi\circ f}X$. Similarly, combine the strong deformation retraction of $W$ onto $M_{\phi}\cup_{F}R_{1}$ with the strong deformation retraction of $M_{\phi}$ onto its top to yield a strong deformation retraction of $W$ onto $Y\cup_{\phi\circ f}X$.

Overall the idea seems right. Any insights will be appreciated.

Thanks!