Oststadt cheap? Wasn't cheap when i last checked 5 years ago...
Without a car, for Coleman:
Sandhofen would be ideal, as there's a direct bus line to the barracks. Schönau, Luzenberg or the northern parts of Neckarstadt would be manageable (tram connection to Sandhofen), Käfertal likely too (bus to Sandhofen). These are all relatively cheap to live in.
The public bus to Coleman (from Sandhofen/Schönau) only runs during peak hours in the morning and afternoon, as far as i know.
http://apps.mhf.dod.mil/pls/psgprod/f?p=10...P6_INST_ID:1750http://home.mannheim.army.mil/sites/local/might also be useful, though it's of course mostly tailored towards the military community.