Well, Frankfurt is not easy sometimes. Be quickly in reserving your room. Into the bargain, its fair week during NODE. That means that towards the weekend prices will get high.
In general: the more out of the city, the better for the price. You can e.g. check hotels in the direction of the town Offenbach. There is a regularly train connection to Offenbach.
Moving around in Frankfurt:
RMV
Stadtplan-FFM
Nachtbus FFM
Nice bars:
If you are looking for a cheap hostel room to share with others you should check the following hostels.
Maybe use the vvvv.org forum to connect yourselfs in advance.
5 elements hostel
Frankfurt Hostel
United Hostel Frankfurt
Haus der Jugend
Jugend Gästeetage
Private couches and accommodations:
couchsurfing
bewelcome
9Flats
airbnb
homeaway
tripping
globalfreeloaders
hospitalityclub
wimdu
In german only:
fewo24
lastminute-privat