The answer to your question is, essentially, yes.  The use of birthday paradox algorithms in the second stage of ECM is standard, and this can be done space efficiently using a random walk approach.   The usual Pollard rho algorithm requires some minor modifications (using a slightly different choice of random walk, as you suggested), which are described in detail in section 6 of Brent's 1986 paper *[Some integer factorization algorithms using elliptic curves][1]*.


  [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.126.5687