I know there is an accepted answer already, but imho it does not meet the second requirement that was asked for. In the above case, strtotime would yield yesterday if used on a wednesday. So, just to be exact you would still need to check for this:
$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;
As davil pointed out in his comment, this was kind of a quick-shot of mine. The above calculation will be off by one once a year due to daylight saving time. The good-enough solution would be:
$tuesday = date('W', $tuesday)==date('W') ? $tuesday-7*86400+7200 : $tuesday;
If you need the time to be 0:00h, you'll need some extra effort of course.