You have not indicated the voltage you will power the relay with, nor have you indicated whether the relay will be normally energized or de-energized during normal operation.
For this reason you will require a single-pole, double-throw (SPDT)contact on the relay (most will come with double-pole, double-throw contacts). The current required for the solenoid valve will be 3.5 / 24 = 0.1456 amperes. Most small relays have contacts rated for 5 amps.
The coil voltage of the relay must be rated for the voltage you will control the relay with.
Incidentally, you should place a diode (wired in reverse to the polarity of the wires across the relay contact, serving the solenoid valve. This will prevent a high voltage spike across the contact, when the solenoid valve is de-energized. This will prevent the contact from burning or welding together.
EDIT
Forgot the fuse/circuit breaker question.
A circuit breaker will be better.It will eliminate the replacing (buying) fuses.
Edit
I would use the relay you have (6 a contact), and place an in-line fuse-holder just downstream of the relay contact. They are cheap (in the USA), and the fuse can be easily and quickly changed.
TexMav