It is possible, yes! Inherently, there's nothing preventing this from happening. You can even do it with browser clients, as JS has built in asymmetric key handling and message signing functions these days.
However, it may noticeably impact performance, especially if you use very large keys. All mainstream secure communication channels use symmetric rather than asymmetric cryptography for the bulk data (messages), because it is many times as fast (and even so, prior to AES native instructions in CPUs, it caused non-trivial CPU load on servers). Both creating and verifying asymmetric signatures is computationally expensive (how much so for each operation depends on the algorithm and the key size), and hardware acceleration for the purpose is usually unavailable. If you decide to do this, I recommend simulating the load it puts on your clients and servers (it will also slightly increase network traffic, though probably not enough to matter) before rolling it out to production. You also probably want to use ECDSA (or rather, Ed25519), rather than something like RSA or integer DSA, as secure key sizes are much smaller and faster.
Note also that you'll still have to solve the key distribution problem. Unless your clients will have their private key present in every one of their devices, they won't be able to use the service. It's important that creating and setting new public keys be a process that requires the verified proof of the client's consent, otherwise a malicious server admin (or similar) could add a new public key (one they just created) to a user's account, and then forge signatures "from that user" as non-repudiable traffic. One option here is Public Key Infrastructure (certificate authorities verifying identity in response to certificate signing requests, and issuing signed certificates containing the public keys) but there are options besides PKI as well (web of trust, external authenticated key server that has the role of a CA but doesn't issue certs per se, probably others).
You should send your traffic over TLS anyhow (you mention headers, so presumably HTTPS), with optional client certificates, for the sake of the server authentication, encryption, built-in replay protection, etc. You'll also need to think carefully about your signing scheme, especially if you have browser clients, as web content isn't allowed to even see, much less set, all headers (e.g. scripts can't see any cookie that is marked HttpOnly). Headers (most notably Content-Length) also change depending on the message; if you're not careful, adding the signature to the message could itself invalidate the signature as some of the signed data changes. You should also consider whether you want this to be bi-directional, or only require request (not response) signing.
Think carefully whether this is worth gaining non-repudiation.