You generally can't name most types that implement the Fn* traits, so in general you can't do this (and putting a type parameter which is constrained on one of those traits is therefore I'll advised). There are, however, two types which you can name: fn() and Box<dyn Fn()>, the latter of which you've already decided against. The former seems like the better option, however it has some downsides too:
You can't capture anything in the closure.
You miss out on function inlining as is done when the type is a definite function (look up function items vs function pointers).
It’s “cheating” a bit, since this adds a new method to all possible Fn<F> types while only returning a particular Foo<{type of the “|| {}” closure}> type.
I’m guessing that your working on some actual use case and that use-case might require multiple Foo structs with different cb functions to have the same type. If this is the case you might need trait objects or at least function pointers anyways.
This will cause type-inference issues, though. But it is indeed the starting point of the only non-dyn-based solution in stable Rust until we get min_type_alias_impl_trait.
I've discussed about this very pattern (impl Fn and returning such from an impl … { fn new() constructor) in this other post:
I have also written a more general-purpose post (impl ArbitraryTrait from a function yielding an opaque type, such as -> impl Iterator…), listing all the current solutions to the problem (nightly feature, constructor with pseudo impl_Trait hidden type, dyn-erasure):