Agile processes are often paper-based, but this makes some basic assumptions that might not be true in a corporate environment.
Even if your team is distributed you can still use pens and paper (with a color scanner) or a white board (with a cheap digital camera). Capturing the images this way can be more agile than trying to use more specialized software tools because you tend to focus on solving the problem, rather than driving the tool, or tweaking the visual presentation.
How do I design my test cases when there aren't any code yet?
From what basis do I have to design them?
From simple assumptions? From the initial requirements?
You start from the user story informed by the initial requirements and discussions with the "on-site customer" if you're lucky enough to have one.
The idea is that you write the test before the code, so that you know when you've finished. The code might not run correctly, or even compile, from the point that you start writing the test until the point where the test runs and passes. This is similar to traditional "test last" development, except that the time that the code is broken tends to be shorter, and you're guaranteed to have a test at the end.
It changes the way that development is motivated from "What code shall I write next?" to "What test shall I write next?". The second question is easier to answer as long as you have a basic idea of what it is that you want to do.