Short answer is: you can.
Tokio is more like "node.js for Rust" or "the Go runtime for Rust".
The bit about Tokio & futures is how you use Tokio today. Tasks are defined as futures, and Rust futures are FSMs. So, a protocol can be implemented as a FSM completely independently of Tokio / futures and then used from Tokio.
In Tokio's next major release (coming soon), it will work with Rust's async fn feature (which is also about to hit stable).
Hope that clarifies things.