Esta es la solución más acertada que te podemos aportar, pero primero estúdiala detenidamente y valora si es compatible a tu trabajo.
Solución:
La mayoría de estas respuestas son demasiadas o técnicamente incorrectas porque “el martes pasado” no significa necesariamente el martes de la semana pasada, solo significa el martes anterior, que podría estar dentro de la misma semana de “ahora”.
La respuesta correcta es:
strtotime('tuesday last week')
Sé que ya hay una respuesta aceptada, pero en mi humilde opinión, no cumple con el segundo requisito que se solicitó. En el caso anterior, strtotime daría como resultado ayer si se usa un miércoles. Entonces, para ser exactos, aún necesitarías verificar esto:
$tuesday = strtotime('last Tuesday');
// check if we need to go back in time one more week
$tuesday = date('W', $tuesday)==date('W') ? $tuesday-7*86400 : $tuesday;
Como señaló davil en su comentario, esta fue una especie de disparo rápido mío. El cálculo anterior se desviará en uno una vez al año debido al horario de verano. La solución suficientemente buena sería:
$tuesday = date('W', $tuesday)==date('W') ? $tuesday-7*86400+7200 : $tuesday;
Si necesita que el tiempo sea 0:00 h, necesitará un esfuerzo adicional, por supuesto.
PHP en realidad lo hace muy fácil:
echo strtotime('last Tuesday');
Ver el strtotime documentación.