You'll find plentiful rooms (''Sobe'') outside the wall of Stari Grad ranging from 10 euro per person per night in the off-season to as much as 30 euro per person per night in the summer. Hotels can be 200 euro and up during high season.
The [http://www.hippohostel.com/ ''Hippo Hostel''] in ''IV Proleterska'' is a pretty cool backpackers hostel for EUR 12 € per night.
Sleeping on the beach might get you into trouble with the police.