Paging is a non-contiguous, fixed size partitioning method to allocate memory to a process. The process(virtual address space/virtual memory) is divided into fixed size partitions(pages) and then loaded into main memory. This post explains why page size is the same as frame size. A page is not the same as a frame, as a page refers to a partition of virtual memory whereas a frame is a partition of physical memory, which holds a page.
A cache block/cache line is a fixed size partition of the cache, which exploits [locality of reference][2]. A cache is an optimization, an effort to reduce the effective memory access time. A system can work perfectly fine without a cache, just slower.
Are they related? Yes and No. The idea of partitioning in both concepts is similar, however their purposes and working are entirely different. The main memory is an addressable memory and needs an address translation mechanism to work with paging, whereas the cache is a content addressable memory, it doesn't have addresses of its own and uses Cache mapping techniques to place data in cache. The size of a cache block is generally not equal to page size.
Do they both exist at the same time? Yes and No, in modern computer systems, Yes. However, no one can stop you from building your own system without paging and caching, or keeping either of them or both.