Yes Febuary should be pretty safe without reservations. Not sure what your tastes are but try Hotel Real or Hotel Sol (in Toledo) which are decent hotels for not too much $$ and are nicely located just inside the walls of the old city.