You can sample from the product $Ax$ in the following way:

Sample a row of $A$ and multiply by $x$. To save memory, forget the row. Sample another row of $A$ and multiply by $x$. To save memory, forget the row. And so on.