It's not clear what you mean by "separate layers," but from your question I'll assume you mean that -drawRect: is currently a big, complicated function that does lots of calculations and so is running too slowly because it gets called a lot. You don't mention CALayer, so I assume you don't mean actual layers here.
The solution to this is to move your calculations out of -drawRect:. You should calculate everything you need only when the data actually change. In -drawRect: you should then use the pre-calculated values, which should be much faster.
For example, since you mention Core Graphics, I assume you're using things like CGPath. You should calculate your CGPath only when the data change, and then store the CGPath in an ivar. You should just draw your CGPath in -drawRect:. If the CGPath is particularly complex (and therefore slow), you may even want to pre-render it into a CGImage and then just composite the CGImage.
Where possible on the iPhone, you should avoid Core Graphics entirely, and instead pre-render the images in Photoshop and save them in your Resources folder. The 3G just doesn't have to computing power to keep up with complex Core Graphics processing. This is a reversal of Apple's recent recommendations on Mac, which discourages the use of pre-rendered images and encourages gradients and paths, and with the 3GS it is less critical because of the much faster processor, but still it's the current recommendation for iPhone, and probably will be until they release a higher-resolution iPhone display. This is of course impossible if you have a dynamic image, but you should keep it in mind for static images.
EDIT:
First, if practical, make sure that you're only drawing those parts that are dirty. -drawRect: passes you a dirty rectangle. If a particular element does not intersect that rectangle, then you don't need to redraw it. Similarly, you should use -setNeedsDisplayInRect: to indicate which pieces need updating. If you can easily break your view into non-overlapping rectangles (or occasionally overlapping rectangles), then this works well.
If you have a view that is made up of various overlapping components that you would like to calculate independently, then you can draw each on a CALayer, and then attach the layers to the view (probably drawing nothing on the view itself). You can then call -setNeedsDisplay on just the layers that have changed. This is what I would probably use for the example of a vertical line. I'd create a CALayer the width of the line and height of the view, set its background color to the line color, and attach it to the view at the position desired. Then moving the line is very fast (or even rotating it using a transform), and it's trivial to remove the line later. If you want fancier line drawing (anti-aliasing and the like), you can of course make the layer wider and actually draw the line inside of the layer. The layer can be as big as the view if needed.
The Core Animation Programming Guide has extensive documentation on CALayer and how to use it.